跳到主要内容

搜索-FloodFill

AcWing 1099.池塘计数​

题目​

链接：https://www.acwing.com/problem/content/1099/

思路-dfs​

遍历每个点，如何这个点为'W'，那么就dfs进去将整个连通块的点都设置为'.'，答案+1，直到遍历完为止

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;

const int N = 1010;
char g[N][N];
bool st[N][N];
int n, m;


void dfs(int a, int b) {
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            int x = a + i, y = b + j;
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (g[x][y]=='W'){
                g[x][y]='.';
                dfs(x,y);
            }
        }
    }
}


signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == 'W') {
                dfs(i, j);
                res++;
            }
        }
    }
    cout<<res<<endl;

    return 0;
}

思路-bfs​

用队列存储点，每次访问过打上标记即可

代码​

#include <bits/stdc++.h>

#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
char g[N][N];
bool st[N][N];
int n, m;

void bfs(int startx, int starty) {
    queue<PII> q;
    q.push({startx, starty});
    st[startx][starty] = true;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                int x = t.first + i, y = t.second + j;
                if (x < 1 || x > n || y < 1 || y > m) continue;
                if (!st[x][y] && g[x][y] == 'W') {
                    q.push({x, y});
                    st[x][y] = true;
                }
            }
        }
    }
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == 'W' && !st[i][j]) {
                bfs(i, j);
                res++;
            }
        }
    }
    cout<<res<<endl;

    return 0;
}

AcWing 1097. 池塘计数​

题目​

题目链接：https://www.acwing.com/problem/content/1099/

思路​

本题为Flood Fill算法的模板题

  • W表示含有雨水，.表示不含有雨水
  • st[]数组表示该点是否被搜过了
  • 主体思路就是：对于一个点，遍历它四周的点，如果有W，就把它加到队列里面，然后继续判断队列里面的点

代码​

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define sc scanf
#define pr printf

const int N = 1010, M = N * N;
int n, m;
char g[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy) //输入的是起点
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = 1;
    while (hh <= tt)
    {
        PII t = q[hh++];

        for (int i = t.x - 1; i <= t.x + 1; i++)
            for (int j = t.y - 1; j <= t.y + 1; j++)
            {
                if (i == t.x && j == t.y)
                    continue;
                if (i < 0 || i >= n || j < 0 || j >= m)
                    continue;
                if (g[i][j] == '.' || st[i][j])//如果这个点不含有雨水，或者这个点已经被搜过
                    continue;
                q[++tt] = {i, j};
                st[i][j] = 1;
            }
    }
}

int main()
{
    sc("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        sc("%s", g[i]);

    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                cnt++;
            }
    pr("%d\n", cnt);
    return 0;
}

AcWing 1098. 城堡问题​

题目链接：https://www.acwing.com/problem/content/1100/

思路​

  • 用BFS求连通块的个数，然后再用BFS求连通块的最大面积 方向数组：

    • dx[]一般表示行
    • dy[]一般表示列

    西墙表示:1,北墙表示:2,东墙表示:4,南墙表示:8 可以看出依次是202^0,212^1,222^2,232^3所以可以用二进制来表示墙的分布情况. 例如:(0101)2(0101)_2表示南,北边无墙,东,西边有墙

    • x>>i&1 :判断二进制表示下的x的第i位是不是1

代码​

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define sc scanf
#define pr printf

const int N=55,M=N*N;

int n,m;
int g[N][N];
PII q[M];
bool st[N][N];

int bfs(int sx,int sy)
{
    int dx[4]={0,-1,0,1};
    int dy[4]={-1,0,1,0};
    int hh=0,tt=0;
    int area=0;
    q[0]={sx,sy};
    st[sx][sy]=1;
    while (hh<=tt)
    {
        PII t=q[hh++];
        area++;
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m) continue;//越界
            if(st[a][b]) continue;//已经被搜索过
            if(g[t.x][t.y]>>i&1) continue;//遇到墙跳过
            q[++tt]={a,b};
            st[a][b]=1;
        }
    }
    return area;
    
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    
    int cnt=0,area=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(!st[i][j])
            {
                area=max(area,bfs(i,j));//房间的最大数量
                cnt++;//连通块数量
            }
    pr("%d\n%d",cnt,area);
    return 0;
}

AcWing 1106. 山峰和山谷​

题目链接：https://www.acwing.com/problem/content/1108/

思路​

根据题目描述

1、没有比它高的叫山峰

2、没有比它矮的叫山谷

3、还存在又比它高，又比它矮的不算山峰也不算山谷

代码​

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define sc scanf
#define pr printf

const int N = 1010, M = N * N;
int n;
int h[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy, bool &has_higher, bool &has_lower)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = 1;

    while (hh <= tt)
    {
        PII t = q[hh++];

        for (int i = t.x - 1; i <= t.x + 1; i++)
            for (int j = t.y - 1; j <= t.y + 1; j++)
            {
                if (i == t.x && j == t.y) continue;//中心格子不用看
                if (i < 0 || i >= n || j < 0 || j >= n)  continue;//越界
                if (h[i][j] != h[t.x][t.y]) //山脉的边界
                {
                    if (h[i][j] > h[t.x][t.y]) has_higher = true;//有比它大的
                    else has_lower = true;//有比它小的
                }
                else if (!st[i][j]) //如果这个点没有被搜过
                {
                    q[++tt] = {i, j};
                    st[i][j] = 1;
                }
            }
    }
}

int main()
{
    sc("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sc("%d", &h[i][j]);
    int peak = 0, valley = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (!st[i][j])
            {
                bool has_higher = false, has_lower = false;
                bfs(i, j, has_higher, has_lower);
                if (!has_higher) peak++;//没有比它更大的了，说明是山峰
                if (!has_lower) valley++;//没有比它更小的了，说明是山谷
            }
    pr("%d %d\n", peak, valley);
    return 0;
}

AcWing 1076. 迷宫问题​

题目链接：https://www.acwing.com/activity/content/problem/content/1471/

思路​

这道题不仅仅需要找到最短距离，还需要保存一下路径，所以开一个pre数组，记录路径

搜索的时候从(n - 1, n - 1)向(0, 0)搜寻 ----- 便于方案的打印(可理解为前者元素为后续元素的前驱)

代码​

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define sc scanf
#define pr printf

const int N=1010,M=N*N;
int n;
int g[N][N];
PII q[M];
PII pre[N][N];//存储当前位置的前驱

void bfs(int sx,int sy)
{
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    int hh=0,tt=0;
    q[0]={sx,sy};
    memset(pre,-1,sizeof pre);
    pre[sx][sy]={0,0};
    while (hh<=tt)
    {
        PII t=q[hh++];

        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=n) continue;  //越界
            if(g[a][b]) continue;//1代表是墙，走不通
            if(pre[a][b].x!=-1) continue;//不是初始化的-1，说明已经被搜索过了
            q[++tt]={a,b};
            pre[a][b]=t;//存储一下当前合理位置的前驱,即该位置由哪个位置引入
        }
    }
    
}

int main()
{
    sc("%d",&n);

    for(int i=0;i<=n;i++)
        for(int j=1;j<=n;j++)
            sc("%d",&g[i][j]);
    
    bfs(n-1,n-1);
    PII end(0,0);
    while (true) //从(n - 1, n - 1)向(0, 0)搜寻
    {
        pr("%d %d\n",end.x,end.y);
        if(end.x==n-1&&end.y==n-1) break;//搜索到最后了
        end=pre[end.x][end.y];//找上一个点
    }
    return 0;
    
}

AcWing 188. 武士风度的牛​

题目链接：https://www.acwing.com/problem/content/190/

思路​

模板题，不解释

代码​

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define sc scanf
#define pr printf

const int N=155,M=N*N;
int n,m;
char g[N][N];
PII q[M];
int dist[N][N];

int bfs()
{
    int dx[]={-2,-1,1,2,2,1,-1,-2};
    int dy[]={1,2,2,1,-1,-2,-2,-1};
    int sx,sy;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='K') sx=i,sy=j;
    int hh=0,tt=0;
    q[0]={sx,sy};
    memset(dist,-1,sizeof dist);
    dist[sx][sy]=0;
    while (hh<=tt)
    {
        PII t=q[hh++];
        for(int i=0;i<8;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m) continue;//越界
            if(g[a][b]=='*') continue;//是障碍物
            if(dist[a][b]!=-1) continue;//被搜索过了
            if(g[a][b]=='H') return dist[t.x][t.y]+1;//到目标点了
            dist[a][b]=dist[t.x][t.y]+1;
            q[++tt]={a,b};
        }
    }
    return -1;
    
}

int main()
{
    sc("%d%d",&m,&n);
    for(int i=0;i<n;i++) cin>>g[i];
    cout<<bfs()<<endl;
    return 0;
}

AcWing 1100. 抓住那头牛​

题目链接：https://www.acwing.com/problem/content/1102/

思路​

有三种情况，每次都扩展题目里的三种状态就行了。为了不出现死循环，这里要判个重。如果之前有步数记录，则说明走过这个地方，不考虑。

代码​

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define sc scanf
#define pr printf

const int N=1e5+10;
int n,k;
int q[N];
int dist[N];

int bfs()
{
    memset(dist,-1,sizeof dist);
    dist[n]=0;
    q[0]=n;
    int hh=0,tt=0;
    while (hh<=tt)
    {
        int t=q[hh++];
        if(t==k) return dist[k];
        if(t+1<N &&dist[t+1]==-1)
        {
            dist[t+1]=dist[t]+1;
            q[++tt]=t+1;
        }
        if(t-1>=0&&dist[t-1]==-1)
        {
            dist[t-1]=dist[t]+1;
            q[++tt]=t-1;
        }
        if(t*2<N&&dist[t*2]==-1)
        {
            dist[t*2]=dist[t]+1;
            q[++tt]=t*2;
        }
    }
    return -1;
    
}


int main()
{
    cin>>n>>k;
    cout<<bfs()<<endl;
    return 0;
}
0%