Rope in the Labyrinth
Time Limit:500MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
A labyrinth with rectangular form and size m × n is divided into square cells with sides' length 1 by lines that are parallel with the labyrinth's sides. Each cell of the grid is either occupied or free. It is possible to move from one free cell to another free cells that share a common side with the cell. One cannot move beyond the labyrinth's borders. The labyrinth is designed pretty specially: for any two cells there is only one way to move from one cell to the other. There is a hook at each cell's center. In the labyrinth there are two special free cells, such that if you can connect the hooks of those two cells with a rope, the labyrinth's secret door will be automatically opened. The problem is to prepare a shortest rope that can guarantee, you always can connect the hooks of those two cells with the prepared rope regardless their position in the labyrinth.
Input
The first line contains integers n and m (3 ≤ n, m ≤ 820). The next lines describe the labyrinth. Each of the next m lines contains ncharacters. Each character is either "#" or ".", with "#" indicating an occupied cell, and "." indicating a free cell.
Output
Print out in the single line the length (measured in the number of cells) of the required rope.
Sample Input
| input | output |
|---|---|
7 6 |
8 |
题目大意：给你一个图，"."表示你可以走，"#“表示墙不能走，每个格子都有一个钩。任意两个格子之间只有一条路，现在问你最短能让所有"."的格子中的钩能用绳子连接的绳子长度。
解题思路：其实就是让你求树的直径的。由"."构成的是一棵树，然后求树的直径，两次广搜即可。
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
typedef long long LL;
const int maxn = 900;
char Map[maxn][maxn];
bool vis[maxn][maxn];
int f[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
struct Node{
int x,y,step;
};
queue<Node>Q;
bool jud(int i,int j){
Node st;
int ret = 0;
if(Map[i-1][j] == '#'){
ret++;
}
if(Map[i][j-1] == '#'){
ret++;
}
if(Map[i+1][j] == '#'){
ret++;
}
if(Map[i][j+1] == '#'){
ret++;
}
if(ret >= 3){
st.x = i, st.y = j, st.step = 0;
Q.push(st);
return true;
}
return false;
}
int n,m;
Node BFS(){
Node st,tmp,en;
en = Q.front();
vis[en.x][en.y] = 1;
while(!Q.empty()){
st = Q.front();
Q.pop();
if(st.step > en.step){
en = st;
}
int tmpx ,tmpy;
for(int i = 0; i < 4; i++){
tmp.x = st.x + f[i][0];
tmp.y = st.y + f[i][1];
if(tmp.x <= 0 ||tmp.x > m ||tmp.y <= 0 || tmp.y > n || Map[tmp.x][tmp.y] =='#' ||vis[tmp.x][tmp.y]){
continue;
}
vis[tmp.x][tmp.y] = 1;
tmp.step = st.step + 1;
Q.push(tmp);
}
}
return en;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
while(!Q.empty()) Q.pop();
for(int i = 1; i <= m; i++){
getchar();
for(int j = 1; j <= n; j++){
scanf("%c",&Map[i][j]);
}
}
int flag = 0;
for(int i = 1; i <= m; i++){
if(flag) break;
for(int j = 1; j <= n; j++){
if(Map[i][j] == '.' && flag == 0){
flag = jud(i,j);
}
if(flag) break;
}
}
Node st = BFS();
memset(vis,0,sizeof(vis));
// printf("%d %d %d+++\n",st.x,st.y,st.step);
st.step = 0;
Q.push(st);
Node en = BFS();
printf("%d\n",en.step);
}
return 0;
}