dfs只能找能否到达，不能找最短距离

要注意把判断障碍物的if(g[x][y]==’#’) return 0; 放到循环外写，因为可能终点在障碍物上

#include <iostream>
#include <cstring>

using namespace std;

const int N=110;

int n,T;

int st[N][N];
char g[N][N];
int sx,sy,ex,ey;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

int dfs(int x,int y)
{
    if(g[x][y]=='#') return 0;
    if(x==ex &&y==ey) return 1;

    st[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a<0||a>=n||b<0||b>=n) continue;
        if(st[a][b]) continue;
        //if(g[a][b]=='#') continue;
        if(dfs(a,b)==1) return 1;
    }

    return 0;
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>g[i][j];
            }
        }

        cin>>sx>>sy>>ex>>ey;
        memset(st,0,sizeof st);

        if(dfs(sx,sy)==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

    }
    return 0;
}

二刷 遇到了一点问题

1. 循环里要是if(dfs(a,b)==1) return 1; 而不能是dfs(a,b)，因为下一层的返回1之后，这一层也要紧跟着直接返回1
2. 不需要回复现场，即不需要st[a][b]=0要一直往下走，因为该题不是枚举所有方案，因此回复现场会超时！！

#include <iostream>
#include <cstring>

using namespace std;

const int N=110;
char g[N][N];
int st[N][N];
int T,n,sx,sy,ex,ey;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int dfs(int x,int y)
{
    if(g[x][y]=='#') return 0;
    if(x==ex&&y==ey) return 1;
    st[x][y]=1;
    for(int i=0;i<4;i++)
    {
        //cout<<"aaa"<<endl;
        int a=x+dx[i];
        int b=y+dy[i];
        if(a<0||a>=n||b<0||b>=n) continue;
        if(g[a][b]=='#'||st[a][b]==1) continue;
        //cout<<a<<" "<<b<<endl;
        if(dfs(a,b)==1) return 1;
        //st[a][b]=0
    }
    return 0;
}

int main()
{
    cin>>T;
    while(T--)
    {
        memset(st,0,sizeof st);
        cin>>n;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>g[i][j];
            }
        }
        cin>>sx>>sy>>ex>>ey;
        //st[sx][sy]=1;
        if(dfs(sx,sy)==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;


    }

    return 0;
}

三刷，直接写的，算是写出来了，但是有点丑

由于对递归函数返回值掌握的不是很清楚，搞了一个全局变量res，有解时把res赋成1

后来复习过后，发现可以在dfs函数里直接这样写：

    if(g[x][y]=='#') return 0;
    if(x==ex&&y==ey) return 1;
    for(int i=0;i<4;i++)
    {
        ....
        if(dfs(a,b)==1) return 1;
    }
    return 0;

#include <iostream>
#include <cstring>

using namespace std;

const int N=1010;
int T,n;
int sx,sy,ex,ey;
char g[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int res;
int st[N][N];

int dfs(int x,int y)
{
    if(g[x][y]=='#' || g[ex][ey]=='#') return 0;
    if(x==ex && y==ey)
    {
        res=1;
        return 1;
    }

    st[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=0 && a<n && b>=0 &&b<n &&g[a][b]=='.' && st[a][b]==0)
        {
            dfs(a,b);
        }
    }

    return 0;
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>g[i][j];
            }
        }
        cin>>sx>>sy>>ex>>ey;
        res=0;
        memset(st,0,sizeof st);
        dfs(sx,sy);
        if(res==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

    }

    return 0;
}

2023/12/1

dfs第一题，复习，忘了
递归函数返回值需要注意
这次是用一个st数组实现的

#include <iostream>
#include <cstring>

using namespace std;

const int N=110;

int n,T;
char g[N][N];
int st[N][N];
int ax,ay,bx,by;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

void dfs(int x, int y)
{
    if(g[x][y] == '#') return;


    st[x][y] = 1;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];

        if(a<0 || a>=n || b<0 || b>=n) continue;
        if(st[a][b]) continue;
        if(g[a][b] == '#') continue;

        dfs(a,b);
    }
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(st, 0, sizeof(st));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>g[i][j];
            }
        }
        cin>>ax>>ay>>bx>>by;

        dfs(ax, ay);

        if(st[ax][ay] && st[bx][by])
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
}