麻将游戏
Time Limit:1s Memory Limit:1024k
Total Submit:3119 Accepted:531
下载样例程序(PE)
下载样例程序(ELF)
--------------------------------------------------------------------------------
Problem
在一种"麻将"游戏中，游戏是在一个有W＊H格子的矩形平板上进行的。
每个格子可以放置一个麻将牌，也可以不放（如图所示）。玩家的目标是将平板上的所有可通过一条路径相连的
两张相同的麻将牌，从平板上移去。最后如果能将所有牌移出平板，则算过关。
这个游戏中的一个关键问题是：两张牌之间是否可以被一条路径所连接，该路径满足以下两个特性：
1. 它由若干条线段组成，每条线段要么是水平方向，要么是垂直方向。
2. 这条路径不能横穿任何一个麻将牌 (但允许路径暂时离开平板)。
这是一个例子：
在（1，3）的牌和在(4, 4)的牌可以被连接。(2, 3)和(3, 4)不能被连接。
你的任务是编一个程序，检测两张牌是否能被一条符合以上规定的路径所连接。
Input
第一行为一整数N表示有N组测试数据。
每组测试数据的第一行有两个整数w，h （1<=w，h<=75），表示平板的宽和高。
接下来h行描述平板信息，每行包含w个字符，如果某格子有一张牌，则这个格子上有个'X'，否则是一个空格。
平板上最左上角格子的坐标为（1，1），最右下角格子的坐标为（w,h）。
接下来的若干行，每行有四个数x1， y1， x2， y2 ，且满足1<=x1,x2<=w，1<=y1,y2<=h，
表示两张牌的坐标（这两张牌的坐标总是不同的）。
如果出现连续四个0，则表示输入结束。
Output
输出文件中，对于每一对牌输出占一行，为连接这一对牌的路径最少包含的线段数。
如果不存在路径则输出0。
Sample Input
1
5 4
XXXXX
X X
XXX X
XXX
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
Sample Output
4
3
0
Source
sgoi
#include<stdio.h>
#include<string.h>
#include<memory.h>
unsigned char mazemap[77][10];
unsigned char visited[77][10];
#define getmap(x,y) (mazemap[y][x/8]&(1<<(7-x%8)))
#define setmap(x,y) mazemap[y][x/8]|=1<<(7-x%8)
#define blkmap(x,y) mazemap[y][x/8]&=~(1<<(7-x%8))
#define getvis(x,y) (visited[y][x/8]&(1<<(7-x%8)))
#define setvis(x,y) visited[y][x/8]|=1<<(7-x%8)
int width,height;
#define QueMax 5929
typedef struct
{
int data[QueMax][2];
int path[QueMax];
int front,rear,count;
}MyQueue;
MyQueue theque;
void initQueue(MyQueue *que)
{
que->front=que->rear=que->count=0;
}
void EnQueue(MyQueue *que,int x,int y,int path)
{
if(que->count==QueMax)
{
return;
}
que->data[que->rear][0]=x;
que->data[que->rear][1]=y;
que->path[que->rear]=path;
que->rear++;
que->count++;
if(que->rear==QueMax)
que->rear=0;
}
void DeQueue(MyQueue *que,/*out*/int *x,int *y,int *path)
{
if(que->count==0)
{
return;
}
*x=que->data[que->front][0];
*y=que->data[que->front][1];
*path=que->path[que->front];
que->front++;
que->count--;
if(que->front==QueMax)
que->front=0;
}
int EmptyQueue(MyQueue *que)
{
return que->count==0;
}
int getline(char *str)
{
char c;
while(1)
{
c=getc(stdin);
if(c==EOF)return 0;
if(c=='\n')break;
*str++=c;
}
*str='\0';
return 1;
}
void readmap(int w,int h)
{
int i,j;
char buffer[256];
memset(mazemap,0,(h+2)*10);
getc(stdin);
for(i=0;i<h;++i)
{
getline(buffer);
for(j=1;j<=w;++j)
if(buffer[j-1]=='X')
setmap(j,i+1);
}
width=w;
height=h;
}
int pathlen(int x,int y,int x2,int y2)
{
int path=0,scan;
memset(visited,0,(height+2)*10);
setvis(x,y);
initQueue(&theque);
blkmap(x2,y2);
while(x!=x2||y!=y2)
{
path++;
for(scan=x-1;scan>=0&&getmap(scan,y)==0;scan--)
{
if(getvis(scan,y)==0)
{
EnQueue(&theque,scan,y,path);
setvis(scan,y);
}
}
for(scan=x+1;scan<=(width+1)&&getmap(scan,y)==0;scan++)
{
if(getvis(scan,y)==0)
{
EnQueue(&theque,scan,y,path);
setvis(scan,y);
}
}
for(scan=y-1;scan>=0&&getmap(x,scan)==0;scan--)
{
if(getvis(x,scan)==0)
{
EnQueue(&theque,x,scan,path);
setvis(x,scan);
}
}
for(scan=y+1;scan<=(height+1)&&getmap(x,scan)==0;scan++)
{
if(getvis(x,scan)==0)
{
EnQueue(&theque,x,scan,path);
setvis(x,scan);
}
}
if(EmptyQueue(&theque))
{
path=0;
break;
}
DeQueue(&theque,&x,&y,&path);
}
setmap(x2,y2);
return path;
}
int main()
{
int n,w,h,i;
int x1,x2,y1,y2;
scanf("%d",&n);
for(i=0;i<n;++i)
{
scanf("%d%d",&w,&h);
readmap(w,h);
while(1)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1==0&&y1==0&&x2==0&&y2==0)
break;
printf("%d\n",pathlen(x1,y1,x2,y2));
}
}
return 0;
}
终于AC了，AC的感觉真爽~~之前犯了一个逻辑错误，真难找啊~~之前我这样写的：
for(scan=x-1;scan>=0&&getmap(scan,y)==0&&getvis(scan,y)==0;scan--)
{
EnQueue(&theque,scan,y,path);
setvis(scan,y);
}
/*right x*/
for(scan=x+1;scan<=(width+1)&&getmap(scan,y)==0&&getvis(scan,y)==0;scan++)
{
EnQueue(&theque,scan,y,path);
setvis(scan,y);
}
/*up y*/
for(scan=y-1;scan>=0&&getmap(x,scan)==0&&getvis(x,scan)==0;scan--)
{
EnQueue(&theque,x,scan,path);
setvis(x,scan);
}
/*down y*/
for(scan=y+1;scan<=(height+1)&&getmap(x,scan)==0&&getvis(x,scan)==0;scan++)
{
EnQueue(&theque,x,scan,path);
setvis(x,scan);
}
if(EmptyQueue(&theque))
return 0;
DeQueue(&theque,&x,&y,&path);
}
这样会出现‘阻拦扫描’的BUG。
评论