BFS搜索 TLE 已判断地图是否走过 想知道还有别的优化方法嘛！

Rebirth_Yun @ 2023-07-13 19:14:01

#include<bits/stdc++.h>
using namespace std;
char mp[100][100];

struct point //存放坐标
{
    int x,y;
};

int x,y;

bool check(point z,int a,int b) //判断坐标合法
{
    int xx = z.x+a;
    int yy = z.y+b;
    return (xx>=0 && xx<=x && yy>=0 && yy<=y && mp[xx][yy] != '#' );
}

int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//方向为四向

int main()
{
    cin >> x >> y;

    for(register int i=0;i<x;i++)
        for(register int j=0;j<y;j++)
            cin >> mp[i][j];

    x--,y--;//我是从0开始计算 所以坐标-1才能达到这个点

    queue<point>Q;
    Q.push({0,0});//起点0,0
    while (!Q.empty())
    {

        point u = Q.front();
        if(u.x==x&&u.y==y)
        {
            cout << "Yes";
            return 0;
        }
        Q.pop();
        mp[u.x][u.y]='#';//当前位置标记障碍 这样下次不会再来
        for(int i=0; i<4; i++)
        {
            if(check(u,dir[i][0],dir[i][1]))//判断合法
            {
                point v = u;
                v.x+=dir[i][0];
                v.y+=dir[i][1];
                Q.push(v);
            }
        }
    }
    cout << "No"; //没有找到输出
    return 0;
}

by SealMoBurp @ 2023-07-13 19:15:01

@Rebirth_Yun 用DFS

by SealMoBurp @ 2023-07-13 19:15:40

@Rebirth_Yun 如下

#include <bits/stdc++.h>
using namespace std;
int n,m,dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};
char a[105][105];
void dfs(int x,int y){
    if (n == x && m == y){
        cout << "Yes";
        exit(0);
    }
    a[x][y] = '#';
    for (int i = 0;i < 4;i++){
        int nx = dx[i] + x,ny = dy[i] + y;
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == '.') dfs(nx,ny);
    }
}
int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) cin >> a[i][j];
    dfs(1,1);
    cout << "No";
    return 0;
}

by Rebirth_Yun @ 2023-07-13 19:18:43

@Seal_ZhouMoTong

谢谢您的帮助！但是我是BFS太弱了 所以特地找的用BFS题 看这题有BFS标签所以来这里问一问BFS的解法的！

还是再次感谢您能帮助我！ 我应该说清出一些的！

by Rebirth_Yun @ 2023-07-13 19:20:14

我的提交情况

by Rebirth_Yun @ 2023-07-13 19:37:54

最新的提交情况

我知道了我的错误在哪里

我的放置障碍是滞后的

我终于了解这种二维BFS的标记了

列举一个图

可以发现最下面两个点被访问了两次

为了避免这种情况 我们应该即使给下面这个点标记

所以还是开vis 标记好啊！

by zhouzihang1 @ 2023-07-13 19:42:16

@Seal_ZhouMoTong @Rebirth_Yun

本蒟蒻建议用 BFS

AC Code如下

#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
const int N=105;
int n,m;
bool a[N][N],vis[N][N];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
queue<pair<int,int> > q;
bool check(int x,int y)
{
    return a[x][y]&&!vis[x][y];
}
void bfs(int x,int y)
{
    q.push(make_pair(x,y));
    vis[x][y]=1;
    while(!q.empty())
    {
        pair<int,int> head=q.front();
        q.pop();
        int x1=head.first,y1=head.second;
        if(x1==n&&y1==m)
        {
            printf("Yes");
            return;
        }
        for(int i=0;i<4;i++)
        {
            int xx=x1+dx[i];
            int yy=y1+dy[i];
            if(check(xx,yy))
            {
                vis[xx][yy]=1;
                q.push(make_pair(xx,yy));
            }
        }
    }
    printf("No");
}
int main()
{
    char c;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>c;
            if(c=='.') a[i][j]=1;//我习惯把char转成int存 
        }
    }
    bfs(1,1);
    return 0;
}

by Rebirth_Yun @ 2023-07-13 20:02:16

@zhouzihang1

可以queue<pair<int,int> >;存坐标 用结构体的本蒟蒻表示学到了！

感谢佬的BFS代码！