BFS 60 B3625 迷宫寻路
  • 板块题目总版
  • 楼主tlyy11
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/1/25 19:40
  • 上次更新2024/1/25 21:33:11
查看原帖
BFS 60 B3625 迷宫寻路
905019
tlyy11楼主2024/1/25 19:40

#include

#include

#include

using namespace std;

int n, m;

string maze[110];

bool vis[110][110];

int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

bool in(int x, int y) {

return 0 <= x && x < n && 0 <= y && y < m;

}

struct node{

int x, y , d;

node(int _x, int _y, int _d){

    x = _x;

    y = _y;

    d = _d;

}

};

bool bfs(int sx, int sy){

queue<node> q;

q.push(node(sx, sy, 0));

vis[sx][sy] = true;

while(!q.empty()){

    node now = q.front();

    q.pop();

    if(now.x == 1 && now.y == 1){

        return true;
    }

    for(int i = 0; i < 4; i++){
                         
        int tx = now.x + dir[i][0];
                         
        int ty = now.y + dir[i][1];
        if(in(tx,ty) && maze[tx][ty] != '#' && !vis[tx][ty]){
                         
            vis[tx][ty] = true;
                         
            q.push(node(tx,ty,now.d + 1));
                         
        }
                         
    }
                         
}
                         
return false;
                         

}

int main() {

cin >> n >> m;

for (int i = 0; i < n; i++) {

    cin >> maze[i];

}

if(bfs(1, 1)){

	cout << "Yes"<<endl;

} else {

	cout << "No" << endl;

}
return 0;

}

2024/1/25 19:40
加载中...