mdxz114514 @ 2024-02-02 10:55:24

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
char arr[100][100];
int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs(){
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int ns=q.front();
        q.pop();
        int nx=ns/m;
        int ny=ns%m;
        if(nx==n-1&&ny==m-1){
            ans=1;
            return;
        }
        for(int i=0;i<4;i++){
            if(nx+fx[i][0]<n&&nx+fx[i][0]>=0&&ny+fx[i][1]<m&&ny+fx[i][1]>=0){
                if(arr[nx+fx[i][0]][ny+fx[i][1]]=='.'){
                    arr[nx][ny]='#';
                    //cout<<nx+fx[i][0]<<' '<<ny+fx[i][1]<<' '<<i<<endl;
                    q.push((nx+fx[i][0])*m+(ny+fx[i][1]));
                }
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }bfs();
    if(ans)cout<<"Yes";
    else cout<<"No";
}
/*
s=x*m+y;
x=s/m;
y=s%m;
*/

by mdxz114514 @ 2024-02-02 11:05:28

开O2:

1AC,#2#3#4#5#6#7#9#10MLE,#7TLE

不开O2:

1AC,#2#3#4#5#6#7#8#9#10TLE

打错力

by sdyzpf @ 2024-02-02 11:06:49

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0,vis[105][105];
char arr[100][100];
int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs(){
    queue<int>q;
    q.push(0);
    vis[0][0]=1;
    while(!q.empty()){
        int ns=q.front();
        q.pop();
        int nx=ns/m;
        int ny=ns%m;
        if(nx==n-1&&ny==m-1){
            ans=1;
            return;
        }
        for(int i=0;i<4;i++){
            if(nx+fx[i][0]<n&&nx+fx[i][0]>=0&&ny+fx[i][1]<m&&ny+fx[i][1]>=0){
                if(arr[nx+fx[i][0]][ny+fx[i][1]]=='.'&&vis[nx+fx[i][0]][ny+fx[i][1]]==0){
                    arr[nx][ny]='#';
                    //cout<<nx+fx[i][0]<<' '<<ny+fx[i][1]<<' '<<i<<endl;
                    vis[nx+fx[i][0]][ny+fx[i][1]]=1;
                    q.push((nx+fx[i][0])*m+(ny+fx[i][1]));
                }
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }bfs();
    if(ans)cout<<"Yes";
    else cout<<"No";
}

@mdxz114514 记录下已经走过的点，走过就不走了，就可以AC了。

by mdxz114514 @ 2024-02-02 11:13:23

@sdyzpf 只得40分

1#6#8#10AC,

其他全WA

by sdyzpf @ 2024-02-02 11:21:19

@mdxz114514 ?我给你改的代码能A啊，把你的代码再发一下

by sdyzpf @ 2024-02-02 11:24:01

@mdxz114514 看到你代码了，把if里arr改成vis就过了

by mdxz114514 @ 2024-02-02 11:26:12

AC了，此贴结

by mdxz114514 @ 2024-02-02 11:28:52

我写错了