题目描述
blablabla
样例
blablabla
算法1
双端队列BFS
时间复杂度
C++ 代码
// 双端队列BFS
// 思路来源:yxc
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int N = 55;
struct node{
int x , y , step;
};
int n , m;
char g[N][N];
bool st[N][N];
int dx[] = {-1 , 1 , 0 , 0} , dy[] = {0 , 0 , -1 , 1};
deque<node> q;
int bfs(){ // 所有为'X'的点为0,所有为'.'的点为1
int ans = 0;
bool flag = false;
while(q.size()){
auto t = q.front();
q.pop_front();
int x = t.x , y = t.y , step = t.step;
if(g[x][y] == '.' && !flag) flag = true; // 第一次搜到'.',说明第一个色块已经搜完,开始寻找第二个色块。
for(int i = 0 ; i < 4 ; i ++){
int a = x + dx[i] , b = y + dy[i] , c = step;
if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]) continue;
if(g[a][b] == '.'){
st[a][b] = true;
q.push_back({a , b , c + 1});
}
else{
ans = c;
st[a][b] = true;
q.push_front({a , b , c});
if(flag) return ans; // 如果在搜索第二个色块,此时说明已经找到最近的点。
}
}
}
}
int main(){
scanf("%d%d" , &n , &m);
for(int i = 0 ; i < n ; i ++) scanf("%s" , g[i]);
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < m ; j ++)
if(g[i][j] == 'X'){
st[i][j] = true;
q.push_front({i , j , 0});
int ans = bfs();
printf("%d" , ans);
return 0;
}
return 0;
}