70分 求助!!!

B3625 迷宫寻路

papala @ 2024-07-20 15:43:15

#include<bits/stdc++.h>
using namespace std;
const int N = 5100;
int n, m;
struct node {
    int x, y;
} p[N * N];
//queue<pair<int,int> >q;
//pair<int,int> p[N*N];
int head, tail;
char mp[N][N];
bool mk[N][N];
bool flag;
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j]; 
        }
    }
    head = tail = 1; 
    p[tail].x = 1, p[tail].y = 1; 
    tail++;
    mk[p[head].x][p[head].y] = true;
    while (head<tail) {
        for (int i = 0; i < 4; i++) {
            int tx = p[head].x + dx[i];
            int ty = p[head].y + dy[i];
            if (tx < 1 || tx > m || ty < 1 || ty > n) {
                continue;
            }
            if (mp[tx][ty] != '#' && mk[tx][ty] == false) { 
                p[tail].x = tx, p[tail].y = ty ; 
                tail++;
                mk[tx][ty] = true; 
            }
            if (tx == m && ty == n) { 
                flag = true;
                break;
            }
        }
        if (flag) {
            break;
        }
        head++;
    }
    if(flag)cout<<"Yes";
    else cout<<"No";
    return 0;
}

by LHX_18460366315 @ 2024-07-20 15:45:36

@papala 我的代码:

#include<bits/stdc++.h>
using namespace std;

//方向变量 
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};

int n,m,mark[1000][1000];
char Map[1000][1000];

//判断(x,y)是否在地图里面  
bool isinmap(int x,int y){
    return (x > 0 && x <= n && y > 0 && y <= m);
} 

void dfs(int x,int y){
    //到终点直接返回 
    if (x == n && y == m){
        return;
    } 
    //遍历四个方向 
    for (int i = 0;i < 4;i++){
        int next_x = x + dx[i];
        int next_y = y + dy[i];
        //三个条件:在地图内,没有被走过,不是墙 
        if (isinmap(next_x,next_y) &&
            !mark[next_x][next_y] && 
            Map[next_x][next_y] != '#'){
                //标记 
                mark[next_x][next_y] = 1;
                //向下搜索 
                dfs(next_x,next_y); 
        } 
    } 
} 

int main(){
    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> Map[i][j];
        }
    }
    //从起点深搜 
    mark[1][1] = 1;
    dfs(1,1);   //从 map(1,1) 开始 
    if (mark[n][m]) cout << "Yes" << endl;  //走到终点 
    else cout << "No" << endl; 
    return 0;
}

by papala @ 2024-07-20 16:38:10

谢谢(^-^)V


|