60分,求解!

Hgq20130520 @ 2024-07-10 17:24:01

#include<bits/stdc++.h>
using namespace std;
int a[101][101],n,m;
char s;
bool dfs(int x,int y)
{
    if(x==n&&y==m)
    {
        return 1;
    }
    if(x<1)
    {
        return 0;
    }
    if(y<1)
    {
        return 0;
    }
    return dfs(x+1,y)||dfs(x-1,y)||dfs(x,y+1)||dfs(x-1,y-1);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>s;
            if(s=='#')
                a[i][j]=1;
            else
                a[i][j]=0;
        }
    }
    if(dfs(n,m)==1)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}

by gkyabc @ 2024-07-10 17:43:54

#include<bits/stdc++.h>
using namespace std;
int n,m,v[105][105],tx,ty,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},head,tail;
char a[105][105];
struct node{
    int x,y;
}b[10005];
int main(){
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin >> a[i][j];
        }
    }
    head=0;tail=1;
    v[1][1]=1;
    b[1].x=1;
    b[1].y=1;
    while(head<=tail){
        head++;
        for(int i = 0;i<4;i++){
            tx=b[head].x+dx[i];
            ty=b[head].y+dy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&v[tx][ty]==0&&a[tx][ty]!='#'){
                tail++;
                v[tx][ty]=1;
                b[tail].x=tx;
                b[tail].y=ty;
                if(tx==n&&ty==m){
                    cout << "Yes";
                    return 0;
                }
            }
        }
    }
    cout << "No";
    return 0;
}