麻将游戏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 Input15 4XXXXXX XXXX XXXX 2 3 5 31 3 4 42 3 3 40 0 0 0Sample Output430Sourcesgoi#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 5929typedef 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。
评论