BFS,但只有40分

jinhaoyu142857 @ 2024-03-05 18:36:45

#include<bits/stdc++.h>
using namespace std;
bool _map[999][999];
bool is_ok(int n,int m){
    queue<pair<int,int>> q;
    unordered_set<int> is_visit,not_visit;
    q.push({1,1});
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        if(x==n&&y==m){
            return 1;
        }
        if(x+1<=n&&is_visit.find(x+1)==is_visit.end()&&!_map[x+1][y]){
            q.push({x+1,y});
            is_visit.insert(x+1);
        }
        if(x-1>=1&&is_visit.find(x-1)==is_visit.end()&&!_map[x-1][y]){
            q.push({x-1,y});
            is_visit.insert(x-1);
        }
        if(y+1<=m&&not_visit.find(y+1)==not_visit.end()&&!_map[x][y+1]){
            q.push({x,y+1});
            not_visit.insert(y+1);
        }
        if(y-1>=1&&not_visit.find(y-1)==not_visit.end()&&!_map[x][y-1]){
            q.push({x,y-1});
            not_visit.insert(y-1);
        }
    }
    return 0;
}
int main(){
    int n,m;
    cin>>n>>m; 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char s;
            cin>>s;
            if(s=='.')_map[i][j]=0;
            else _map[i][j]=1;
        }
    }
    bool ans=is_ok(n,m);
    if(ans)cout<<"Yes";
    else cout<<"No";
}

by yanhaoming @ 2024-06-28 20:40:08

# include<bits/stdc++.h>
using namespace std;
struct point {
    int x;
    int y;
    void operator=(int a[2]) {
        x = a[0];
        y = a[1];
    }
    void operator=(point b) {
        x = b.x;
        y = b.y;
    }

};

const int xj[4] = {-1, 1, 0, 0};
const int yj[4] = {0, 0, -1, 1};
signed main() {
    point S, E;
    int x, y;
    scanf("%d", &y);
    scanf("%d", &x);
    S.x = 0;S.y = 0;
    E.x = x-1;E.y = y-1;
    int migong[155][155];
    for (int yy = 0; yy < y; yy++) {
        for (int xx = 0; xx < x; xx++) {
            char c;
            cin >> c;

            if (c == '.') {
                migong[xx][yy] = 0;
            }
            if (c == '#') {
                migong[xx][yy] = 1;
            }
        }
    }
    point pts[24111];
    int ptsi = 0;
    pts[ptsi] = S;
    ptsi++;
    migong[S.x][S.y] = -1;
    int flag = 1, cnt = 0;
    while (flag) {
        flag = 0;
        vector<point> newp;

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

            if (pts[i].x == E.x && pts[i].y == E.y) {
                printf("Yes");
                return 0;
            }

            for (int j = 0; j < 4; j++) {
                point wz = pts[i];
                wz.x += xj[j];
                wz.y += yj[j];
                if (wz.x >= 0 && wz.x < x && wz.y >= 0 && wz.y < y && migong[wz.x][wz.y] == 0) {
                    flag = 1;
                    newp.push_back(wz);
                    migong[wz.x][wz.y] = -1;
                }
            }

        }
        ptsi = 0;
        for (int i = 0; i < newp.size(); i++) {
            pts[ptsi] = newp[i];
            ptsi++;
        }
        cnt++;
    }
    printf("No");
    return 0;
}