题目描述
两次BFS
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
char a[N][N];//地图
int d[N][N];
int w[N][N];
int r,c;
int dx[]= {-1,0,1,0};
int dy[]= {0,1,0,-1};
int Jx,Jy,Fx,Fy;
typedef pair<int,int> PI;
queue<PI> q;
queue<PI> f;
void bfs() {
if(Jx==0||Jy==0||Jx==r-1||Jy==c-1) {
cout<<1<<endl;
return ;
}
while(!f.empty()) {
PI u=f.front();
f.pop();
for(int i=0; i<4; i++) {
int x=u.first+dx[i];
int y=u.second+dy[i];
if(x>=0&&x<r&&y>=0&&y<c&&a[x][y]!='#'&&d[x][y]==INF) {
d[x][y]=d[u.first][u.second]+1;
f.push({x,y});
}
}
}
w[Jx][Jy]=0;
q.push({Jx,Jy});
while(!q.empty()) {
PI t = q.front();
q.pop();
for(int i=0; i<4; i++) {
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x>=0&&x<r&&y>=0&&y<c&&a[x][y]=='.'&&w[t.first][t.second]+1<d[x][y]&&w[x][y]==INF) {
w[x][y]=w[t.first][t.second]+1;
q.push({x,y});
if(x==0||y==0||x==r-1||y==c-1) {
cout<<w[x][y]+1<<endl;
return ;
}
}
}
}
cout<<"IMPOSSIBLE"<<endl;
return ;
}
int main() {
int t;
cin>>t;
while(t--) {
memset(d,0x3f,sizeof d);
memset(w,0x3f,sizeof w);
while(!q.empty()) q.pop();
while(!f.empty()) f.pop();
cin>>r>>c;
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
cin>>a[i][j];
if(a[i][j]=='J') {
Jx=i;
Jy=j;
a[i][j]='.';
}
if(a[i][j]=='F') {
Fx=i;
Fy=j;
d[Fx][Fy]=0;
f.push({Fx,Fy});
}
}
}
bfs();
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla