临沂企业网站开发官网,网站申请备案流程,网站制作费用多少,外贸网站如何建站正题 题目大意
一个迷宫#xff0c;有许多出口#xff0c;求一个点到最近的出口最远。 解题思路
直接bfs暴力搜索#xff0c;然后保存上次的答案 code
// luogu-judger-enable-o2
#includecstdio
#includequeue
#includecstring
#define N 210
u…正题 题目大意
一个迷宫有许多出口求一个点到最近的出口最远。 解题思路
直接bfs暴力搜索然后保存上次的答案 code
// luogu-judger-enable-o2
#includecstdio
#includequeue
#includecstring
#define N 210
using namespace std;
struct node{int x,y;
};
const int dx[4]{0,0,1,-1},dy[4]{1,-1,0,0};
int a[N][N],w,h,maxs;
char map[N][N];
queuenode q;
void bfs(int xs,int ys)//搜索
{q.push((node){xs,ys});a[xs][ys]0;while(!q.empty()){node xq.front();q.pop();int wsa[x.x][x.y];for(int i0;i4;i) {int xxdx[i]x.x,yydy[i]x.y;int zxdx[i]*2x.x,zydy[i]*2x.y;if(zxhzx0zywzy0map[xx][yy] a[zx][zy]ws1){q.push((node){zx,zy});a[zx][zy]ws1;}}}
}
int main()
{memset(a,127/3,sizeof(a));scanf(%d%d,w,h);ww*21;hh*21;for(int i0;ih;i){gets(map[i]1);for(int j1;jw;j)if(map[i][j]-||map[i][j]||map[i][j]|)map[i][j];else map[i][j] ;}for(int i1;ih;i){if(map[i][1] )bfs(i,2);if(map[i][w] )bfs(i,w-1);}for(int i1;iw;i){if(map[1][i] )bfs(2,i);if(map[h][i] )bfs(h-1,i);}for(int i1;ih;i)//{for(int j1;jw;j)//{if(a[i][j]707406378)maxsmax(maxs,a[i][j]);//printf(%5d,a[i][j]);//else printf(%5d,100);//}printf(\n);}printf(%d,maxs1);
}
