joj1113

 1113: The Game

Result
TIME Limit
MEMORY Limit
Run Times
AC Times
JUDGE
3s
8192K
380
97
Standard
One morning, you wake up and think: ``I am such a good programmer. Why not make some money?'' So you decide to write a computer game.
The game takes place on a rectangular board consisting of w * h squares. Each square might or might not contain a game piece, as shown in the picture.
One important aspect of the game is whether two game pieces can be connected by a path which satisfies the two following properties:
It consists of straight segments, each one being either horizontal or vertical. 
It does not cross any other game pieces.  (It is allowed that the path leaves the board temporarily.)
Here is an example:
The game pieces at (1,3) and at (4, 4) can be connected. The game pieces at (2, 3) and (3, 4) cannot be connected; each path would cross at least one other game piece.
The part of the game you have to write now is the one testing whether two game pieces can be connected according to the rules above.

Input

The input contains descriptions of several different game situations. The first line of each description contains two integers w and h (1 <= w,h <= 75), the width and the height of the board. The next h lines describe the contents of the board; each of these lines contains exactly w characters: a ``X'' if there is a game piece at this location, and a space if there is no game piece.
Each description is followed by several lines containing four integers x1, y1, x2, y2 each satisfying 1 <= x1,x2 <= w, 1 <= y1,y2 <= h. These are the coordinates of two game pieces. (The upper left corner has the coordinates (1, 1).) These two game pieces will always be different. The list of pairs of game pieces for a board will be terminated by a line containing ``0 0 0 0".
The entire input is terminated by a test case starting with w=h=0. This test case should not be procesed.

Output

For each board, output the line ``Board #n:'', where n is the number of the board. Then, output one line for each pair of game pieces associated with the board description. Each of these lines has to start with ``Pair m: '', where m is the number of the pair (starting the count with 1 for each board). Follow this by ``ksegments.'', where k is the minimum number of segments for a path connecting the two game pieces, or ``impossible.'', if it is not possible to connect the two game pieces as described above.
Output a blank line after each board.

Sample Input

5 4
XXXXX
X   X
XXX X
 XXX
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
0 0

Sample Output

Board #1:
Pair 1: 4 segments.
Pair 2: 3 segments.
Pair 3: impossible.

This problem is used for contest: 149 
Submit / Problem List / Status / Discuss
이 문제는 2558과 차이가 많지 않은 특수한 대기열 응용이다.
나는 이 문제의 난점이 어떻게 출력하는가에 있다고 생각한다.저는 우선 주 함수에서.
우선 일부 특수한 상황에 대해 출력을 하여 bfs의 압력을 경감시킨다.
그리고 bfs에는 두 개의 출력 함수가 각각 다른 상황에 대응한다.
첫 번째 함수는 하나의 직통로에서 통로 양측의 점을 맞출 수 있도록 하는 것이다
목표점이 있는지 분석하여 판단하다
두 번째 함수 목적은 통로의 끝에 있는 그 점을 분석하고 판단하는 데 있다.
(나는 내가 분명히 말하지 못한 것 같아. 그곳이 모르면 나에게 메시지를 남겨도 돼.)
#include
#include
#include
#include
using namespace std;
char map[100][100];
int h,w;
int visited[100][100];
bool success;
class Node
{
public:
int x,y;
int step;
};
bool ok(int x,int y,Node node)
{
//up
if(x-1==node.x&&y==node.y&&map[node.x][node.y]=='X')return true;
//down
if(x+1==node.x&&y==node.y&&map[node.x][node.y]=='X')return true;
//left
if(x==node.x&&y-1==node.y&&map[node.x][node.y]=='X')return true;
//right
if(x==node.x&&y+1==node.y&&map[node.x][node.y]=='X')return true;
return false;
}
int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void bfs(Node node1,Node node2)
{
node1.step=0;
queueq;
q.push(node1);
visited[node1.x][node1.y]=1;
while(!q.empty())
{
Node temp;
temp=q.front();
q.pop();
if(ok(temp.x,temp.y,node2))
{
printf("%d segments.",temp.step+1);
success=false;
return ;
}
node1=temp;
node1.step++;
int x,y;
for(int i=0;i<4;i++)
{
temp=node1;
while(1)
{
x=temp.x+move[i][0];
y=temp.y+move[i][1];
if(x>=0&&x<=h+1&&y>=0&&y<=w+1&&!visited[x][y]&&map[x][y]!='X')
{
visited[x][y]=1;
temp.x=x;
temp.y=y;
temp.step=node1.step;
q.push(temp);
if(x+move[i][0]==node2.x&&y+move[i][1]==node2.y
   &&map[node2.x][node2.y]=='X')
{
printf("%d segments.",temp.step);
success=false;
return ;
}//그 정도
}
else break;
};
}
}
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int n=1;
Node node1,node2;
while(scanf("%d%d",&w,&h),w&&h)
{
memset(map,' ',sizeof(map));
getchar();
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
map[i][j]=getchar();
}
getchar();
}
printf("Board #%d:",n++);
int m=1;
while(1)
{
memset(visited,0,sizeof(visited));
success=true;
scanf("%d%d%d%d",&node1.y,&node1.x,&node2.y,&node2.x);
if(node1.x==0&&node1.y==0&&node2.x==0&&node2.y==0)
break;
printf("Pair %d: ",m++);
if(node1.x==node2.x&&node1.y==node2.y&&map[node1.x][node1.y]=='X')
{printf("0 segments.");success=false;}
else if(map[node1.x][node1.y]!='X'||map[node2.x][node2.y]!='X')
{
printf("impossible.");
success=false;
}//우선 간단한 상황을 분석하여 bfs에서 부담을 줄일 수 있습니다
else bfs(node1,node2);
if(success)printf("impossible.");
}
printf("");
}
return 0;
}