DFS(231ms)

简单套模板就行了, 有一个坑点就是不能回溯,回溯就会TLE

C++ 代码

#include <iostream>
#include<stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
const int N = 100 + 10;
int m,n;
char g[N][N];
int v[N][N];
bool flag;
void dfs(int stx, int sty, int ex, int ey)
{
    v[stx][sty] = 1;
    if(stx == ex && sty == ey)
    {
        flag = true;
        return;
    }
    int dx[4] = {1,-1,0,0} ,dy[4] = {0,0,1,-1};
    for(int i = 0; i < 4; i++)
    {
        int x = stx + dx[i], y = sty + dy[i];
        if(g[x][y] == '.' && x >= 0 && y >= 0 && x < n && y < n && v[x][y] == -1)
        {
            if(flag == true)
                break;
            v[x][y] = 1;
            dfs(x,y,ex,ey);
            //v[x][y] = -1;   //千万不要回溯,否则会tle
        }

    }

}
int main()
{
    cin.tie(0);
    cin>>m;
    while(m--)
    {
        flag = false;
        cin >> n;
        memset(v,-1,sizeof v);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                cin >> g[i][j];
        int stx,sty,ex,ey;
        cin >> stx >> sty;
        cin >> ex >> ey;
        if(g[stx][sty] == '#' || g[ex][ey] == '#')
        {
            cout << "NO" << endl;
            continue;
        }
        dfs(stx,sty,ex,ey);
        if(!flag)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
    return 0;
}

BFS (501ms)

用d[N][N] 来存到终点就距离,初始化为-1, 如果有距离代表能到达

C++ 代码

#include <iostream>
#include<stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
typedef pair<int ,int> pii;
const int N = 100 + 10;
int n, m;
char g[N][N];
int d[N][N];
pii q[N * N];
int bfs(int stx,int sty,int st , int ed)
{
    int tt= 0,hh = 0;
    memset(d,-1,sizeof d);
    d[stx][sty] = 0;
    q[0] = {stx,sty};
    while(hh <= tt)
    {
        pii t = q[hh ++];
        int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
        for(int i = 0;i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && y >= 0 && x < n && y < n && d[x][y] == -1 && g[x][y] == '.')
            {
                q[ ++ tt] = {x,y};
                d[x][y] = d[t.first][t.second] + 1;
            }
        }
    }
    return d[st][ed];
}
int main()
{
    cin>>m;

    while(m-- )
    {
        cin>> n;
        int index_x,index_y,e_x,e_y;
        memset(q,0,sizeof q);
        for(int i = 0; i < n ; i++)
            for(int j = 0; j < n; j++)
                    cin >> g[i][j];

        cin >> index_x >> index_y;
        cin >> e_x >> e_y;

        int flag =   bfs(index_x,index_y,e_x,e_y);
        if(g[e_x][e_y] == '#' || g[index_x][index_y] == '#')
        {
            cout << "NO" << endl;
            continue;
        }
        if(flag == -1)
        {
            cout << "NO" << endl;
        }
        else
            cout << "YES" << endl;
    }
    return 0;
}