算法1: DFS
(暴力枚举) $O(n^2*k)$
一般的深度优先搜索模板,通过一个标记量来标识是否能找到。
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
int n,k;
const int N=105;
char g[N][N];
int a1,b1,a2,b2;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
bool flag[N][N];
bool bound = 0; // 标记量,用于记录是否找到
bool check(int x,int y)
{
return x>=0&&x<n&&y>=0&&y<n&&g[x][y]=='.'&&!flag[x][y];
}
void dfs(int x,int y)
{
if(x==a2&&y==b2)
{
bound = 1;
return;
}
flag[x][y] = 1;
for(int i=0;i<4;i++)
{
int xx = x+dx[i];
int yy = y+dy[i];
if(check(xx,yy))
{
flag[xx][yy]=1;
dfs(xx,yy);
}
}
}
int main()
{
cin>>k;
while(k--)
{
cin>>n;
for(int i=0;i<n;i++) cin>>g[i];
cin>>a1>>b1>>a2>>b2;
memset(flag,0,sizeof flag);
if(g[a1][b1]=='#'||g[a2][b2]=='#')
{
puts("NO");
continue;
}
bound = 0; // 注意此处由于是多组输入,需要重新赋值bound
dfs(a1,b1);
if(bound) puts("YES");
else puts("NO");
}
return 0;
}
算法2 :BFS
(暴力枚举) $O(n^2*k)$
广度优先搜索(相比dfs只改了bfs()函数部分)
C++ 代码
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=105;
int k,n;
int a1,b1,a2,b2;
char g[N][N];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
bool flag[N][N];
bool bound = false; // 标记量,用于记录是否找到
bool check(int x,int y)
{
return x>=0&&x<n&&y>=0&&y<n&&g[x][y]=='.'&&!flag[x][y];
}
void bfs(int x1,int y1)
{
queue<pair<int,int >> q;
q.push({x1,y1});
flag[x1][y1] = 1;
while(!q.empty())
{
auto p = q.front();
q.pop();
int x = p.first;int y = p.second;
if(x==a2&&y==b2) bound = true;
for(int i=0;i<4;i++)
{
int nx = x+dx[i];
int ny = y+dy[i];
if(check(nx,ny))
{
flag[nx][ny] = 1;
bfs(nx,ny);
}
}
}
}
int main()
{
cin>>k;
while(k--)
{
cin>>n;
for(int i=0;i<n;i++) cin>>g[i];
cin>>a1>>b1>>a2>>b2;
if(g[a1][b1]=='#'||g[a2][b2]=='#')
{
cout<<"NO"<<endl;
continue;
}
memset(flag,0,sizeof flag);
bound = false; // 重新初始化bound
bfs(a1,b1);
if(bound==true) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}