|
The Game
Description
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 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. Source |
题意：
连连看的规则。问两个卡之间的最少拐弯数。
思路：
很容易想到bfs但是写到一半时卡了下。因为想到一格一格的走的话不能保证拐弯数是递增的。还想写个优先队列。但是先明白了其实很简单。这里的一步已不再是一个。而是一条线。所以每次处理一个方向的一条线就行了。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=100010;
typedef __int64 ll;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int w,h,head,tail,sx,sy,ex,ey,ans;
char maze[100][100];
int vis[100][100];
struct yb
{
int x,y;
int dre,sp;
} q[10000];
void bfs()
{
int i,x,y,nx,ny,dr;
memset(vis,0,sizeof vis);
vis[sx][sy]=1;
head=tail=0;
q[tail].x=sx;
q[tail].y=sy;
q[tail].dre=4;
q[tail++].sp=0;
while(head<tail)
{
x=q[head].x;
y=q[head].y;
dr=q[head].dre;
if(x==ex&&y==ey)
{
ans=q[head].sp;
break;
}
for(i=0;i<4;i++)
{
if(i==dr)
continue;
nx=x+dx[i];
ny=y+dy[i];
while(nx>=0&&nx<=h+1&&ny>=0&&ny<=w+1&&!vis[nx][ny]&&maze[nx][ny]!='X')//一次处理一条线
{
vis[nx][ny]=1;
q[tail].x=nx;
q[tail].y=ny;
q[tail].sp=q[head].sp+1;
q[tail].dre=i;
tail++;
nx+=dx[i];
ny+=dy[i];
}
if(nx==ex&&ny==ey)
{
ans=q[head].sp+1;
return;
}
}
head++;
}
}
int main()
{
int i,bd=1,pa;
while(scanf("%d%d",&w,&h),w||h)
{
pa=1;
getchar();
memset(maze,0,sizeof maze);
for(i=1;i<=h;i++)
gets(maze[i]+1);
printf("Board #%d:\n",bd++);
while(scanf("%d%d%d%d",&sy,&sx,&ey,&ex),sx||sy||ex||ey)
{
ans=-1;
bfs();
if(ans!=-1)
printf("Pair %d: %d segments.\n",pa++,ans);
else
printf("Pair %d: impossible.\n",pa++);
}
printf("\n");
}
return 0;
}