题目描述
样例
2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3
输出:no
yes
算法1
(bfs)
此题区别于一般的vis数组:此vis数组中记录了上一次访问到此位置时的剩余拐弯次数.如果下一次到该点的时候剩余拐弯次数小于上一次走到该点剩余的拐弯次数那么不会进队列,
此外 此题x1,y1分别代表列和行
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 102;
char a[N][N];
typedef pair<pair<int,int>,pair<int,int>> PII;//存下标和当前剩余的拐弯次数以及当前方向
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
int vis[N][N];//区别于一般的vis数组 此vis数组中记录了上一次访问到此位置时的剩余拐弯次数
int main()
{
int t;cin>>t;
while(t--){
memset(vis, 0, sizeof vis);
int m,n;cin>>m>>n;
for (int i = 0; i < m; i ++ ){
for (int j = 0; j < n; j ++ ){
cin>>a[i][j];
}
}
int k;cin>>k;//表示最多能拐的弯数
int x1,y1;cin>>x1>>y1;//表示起点 特别注意x1,x2对应列, y1,y2对应行
x1-=1;y1-=1;
swap(x1,y1);
int x2,y2;cin>>x2>>y2;
x2-=1;y2-=1;
swap(x2,y2);
queue<PII>que;
que.push({{x1,y1},{-1,k}});
vis[x1][y1]=k;
int temp=0;
//一开始方向为-1 不确定
while(!que.empty()){
PII pii=que.front();
que.pop();
int curx=pii.first.first;
int cury=pii.first.second;
int d=pii.second.first;//表示当前方向
int t=pii.second.second;//表示还剩余的可以拐弯的次数
if(curx==x2&&cury==y2){
cout<<"yes"<<endl;
temp=1;
break;
}
for (int i = 0; i < 4; i ++ ){
int nextx=curx+dir[i][0];
int nexty=cury+dir[i][1];
if(nextx<0||nextx>=m||nexty<0||nexty>=n) continue;
if(d==-1){
//表示第一次进入,随便选一个方向作为开始方向
if(a[nextx][nexty]=='.'){
que.push({{nextx,nexty},{i,t}});
vis[nextx][nexty]=t;//记录此时的拐弯次数
}
}else{
if(d!=i&&t==0) continue;
//如果下一次到该点的时候剩余拐弯次数小于上一次走到该点剩余的拐弯次数
//那么不会金队列
if(d==i&&a[nextx][nexty]=='.'&&vis[nextx][nexty]<=t){
que.push({{nextx,nexty},{d,t}});
vis[nextx][nexty]=t;
}
if(t>=1&&d!=i){
if(a[nextx][nexty]=='.'&&vis[nextx][nexty]<=t){
que.push({{nextx,nexty},{i,t-1}});
vis[nextx][nexty]=t;
}
}
}
}
}
if(!temp){
cout<<"no"<<endl;
}
}
return 0;
}