TLE???

NYNY111 @ 2024-08-02 23:28:11

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
char g[102][102];
struct point{
    int x,y;
};
queue<point>q;
int flag=0;
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    struct point a;
    a.x=1,a.y=1;
    q.push(a);
    while(!q.empty()){
        int x=q.front().x,y=q.front().y;
        q.pop();
        if(x==n&&y==m){
            flag=1;
            break;
        }
        g[x][y]='#';
        for(int i=0;i<4;i++){
            struct point b;
            int xx=x+dir[i][0],yy=y+dir[i][1];
            if(xx<1||xx>n||yy<1||yy>m||g[xx][yy]=='#')continue;
            b.x=xx,b.y=yy;
            q.push(b);
        }
    }
    if(flag)cout<<"Yes";
    else cout<<"No";
    return 0;
}

by Jokersheng @ 2024-08-02 23:33:32

AC代码(也是广搜)：

#include<iostream>
#include<queue>
using namespace std;
int r,c,res,mk[110][110],xy[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
char s[110][110];
struct node {
    int x,y,step;
};
void bfs(int x,int y) {
    mk[x][y] = 1;
    queue<node> q;
    q.push((node){x,y,0});
    while(q.size()) {
        node t = q.front();
        q.pop();
        for(int i = 0;i < 4;i++) {
            int xx = t.x+xy[i][0],yy = t.y+xy[i][1];
            if(xx == r-1 && yy == c-1) {
                cout << "Yes";
                return;
            }
            if(xx >= 0 && xx < r && yy >= 0 && yy < c && s[xx][yy] == '.' && !mk[xx][yy]) {
                mk[xx][yy] = 1;
                q.push((node){xx,yy,t.step+1});
            } 
        }
    }
    cout << "No";
}
int main() {
    cin >> r >> c;
    for(int i = 0;i < r;i++) for(int j = 0;j < c;j++) cin >> s[i][j];
    bfs(0,0);
    return 0;
}

点个关注再走呗