题目不说了。。。
一共三个版本，first——也就是最长的是我写的。second版本当遍历20X20的空棋盘就要死了。。。
Astyle插件真好用。。。
什么？没听说过Astyle？呵呵，用code::blocks吧，很强大！gprof插件也很强大。
#define first #ifdef first #include<stdio.h> #include<stdlib.h> #define MAX_SIZE 100 int row,col,room; int sx,sy,tx,ty; int maza[MAX_SIZE+1][MAX_SIZE+1]; long path[MAX_SIZE+1][MAX_SIZE+1]; /*---------queue.h begins-----------------*/ typedef struct QueueNode { int x; int y; int depth; struct QueueNode* next; } qnode; typedef struct Queue { qnode* head; qnode* tail; } queue; int init(queue* q) { q->head=q->tail=NULL; return 0; } qnode* cnode(int x,int y,int depth) { qnode* node=(qnode*)malloc(sizeof(qnode)); if(!node) puts("error!"); else { node->x=x; node->y=y; node->depth=depth; } return node; } int enqueue(queue* q,int x,int y,int depth) { qnode* node=cnode(x,y,depth); if(q->head==NULL||q->tail==NULL) q->head=q->tail=node; else { q->tail->next=node; q->tail=node; } return 0; } int dequeue(queue* q,int*x ,int*y,int* depth) { if(!q->head||!q->tail) puts("Queue is currently empty!"); if(q->head==q->tail) { *x=q->head->x; *y=q->head->y; *depth=q->head->depth; free(q->head); q->head=q->tail=NULL; } else { qnode* tmp=q->head; *x=tmp->x; *y=tmp->y; *depth=tmp->depth; q->head=tmp->next; free(tmp); } return 0; } int destroy(queue* q) { qnode* tmp; if(!q) puts("error in function destroy"); while(q->head!=q->tail) { tmp=q->head; q->head=tmp->next; free(tmp); } free(q->head); free(q); return 0; } int clear(queue* q) { qnode* tmp; if(!q) puts("error in function destroy"); while(q->head!=q->tail) { tmp=q->head; q->head=tmp->next; free(tmp); } free(q->head); q->head=q->tail=NULL; return 0; } int isEmpty(queue* q) { return q->head==NULL; /*q->tail==NULL is also ok!*/ } /*----------------queue.h ends---------------------*/ int main(void) { scanf("%d%d%d",&row,&col,&room); int i,j,k; for(i=0; i<room; i++) { scanf("%d%d",&j,&k); maza[j][k]=-1; } scanf("%d%d%d%d",&sx,&sy,&tx,&ty); queue* q=(queue*)malloc(sizeof(queue)); init(q); enqueue(q,sx,sy,1); maza[sx][sy]=1; int x,y,depth,found=0; while(!isEmpty(q)) { dequeue(q,&x,&y,&depth); if(x==tx&&y==ty) { found=1; break; } else { if(x-1>=1&&!maza[x-1][y]) enqueue(q,x-1,y,depth+1),maza[x-1][y]=depth+1; if(x+1<=row&&!maza[x+1][y]) enqueue(q,x+1,y,depth+1),maza[x+1][y]=depth+1; if(y-1>=1&&!maza[x][y-1]) enqueue(q,x,y-1,depth+1),maza[x][y-1]=depth+1; if(y+1<=col&&!maza[x][y+1]) enqueue(q,x,y+1,depth+1),maza[x][y+1]=depth+1; } } clear(q); path[sx][sy]=1; enqueue(q,sx,sy,1); while(!isEmpty(q)) { dequeue(q,&x,&y,&depth); if(x-1>=1&&maza[x-1][y]==depth+1) { if(!path[x-1][y]) enqueue(q,x-1,y,depth+1); path[x-1][y]+=path[x][y]; } if(x+1<=row&&maza[x+1][y]==depth+1) { if(!path[x+1][y]) enqueue(q,x+1,y,depth+1); path[x+1][y]+=path[x][y]; } if(y-1>=1&&maza[x][y-1]==depth+1) { if(!path[x][y-1]) enqueue(q,x,y-1,depth+1); path[x][y-1]+=path[x][y]; } if(y+1<=col&&maza[x][y+1]==depth+1) { if(!path[x][y+1]) enqueue(q,x,y+1,depth+1); path[x][y+1]+=path[x][y]; } } destroy(q); if(!found) puts("No Solution!"); else printf("%d/n%ld/n",depth-2,path[tx][ty]); return 0; } #endif #ifdef second #include<stdio.h> #define N 100 int s,map[N+1][N+1]; typedef struct { int x,y; } xy; xy queue[N*N],start,end,last; void depth(int x,int y) { if(map[x][y]==1) { s++; x=last.x; x=last.y; return; } last.x=x; last.y=y; if(x==1&&y==1) return; if(map[x-1][y]==map[x][y]-1) depth(x-1,y); if(map[x+1][y]==map[x][y]-1) depth(x+1,y); if(map[x][y-1]==map[x][y]-1) depth(x,y-1); if(map[x][y+1]==map[x][y]-1) depth(x,y+1); } int main() { int front=0,rear=1; int n,m,k,i,j; scanf("%d%d%d",&n,&m,&k); for(i=0; i<=N; i++) for(j=0; j<=N; j++) map[i][j]=0; while(k--) { scanf("%d%d",&i,&j); map[i][j]=-1; } scanf("%d%d",&start.x,&start.y); scanf("%d%d",&end.x,&end.y); queue[front].x=start.x; queue[front].y=start.y; map[start.x][start.y]=1; while(front<rear) { i=queue[front].x; j=queue[front].y; if(i==end.x&&j==end.y) break; if(i-1>0&&map[i-1][j]==0) { map[i-1][j]=map[i][j]+1; queue[rear].x=i-1; queue[rear].y=j; rear++; } if(j-1>0&&map[i][j-1]==0) { map[i][j-1]=map[i][j]+1; queue[rear].x=i; queue[rear].y=j-1; rear++; } if(i+1<=n&&map[i+1][j]==0) { map[i+1][j]=map[i][j]+1; queue[rear].x=i+1; queue[rear].y=j; rear++; } if(j+1<=m&&map[i][j+1]==0) { map[i][j+1]=map[i][j]+1; queue[rear].x=i; queue[rear].y=j+1; rear++; } front++; } if(front==rear) printf("No Solution!/n"); else { s=0; last.x=i; last.y=j; printf("%d/n",map[i][j]-1); depth(i,j); printf("%d/n",s); } return 0; } #endif #ifdef third #include <stdio.h> int count[1001][1001]; int que[2][1000000][2]; int main(void) { int n,m,k; int i,j,x,y,startx,starty,endx,endy,step,flag1,flag2,l[2],tx,ty; int dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1}; while(scanf("%d %d %d",&n,&m,&k)!=EOF) { for(i=1; i<=n; i++) for(j=1; j<=m; j++) count[i][j]=0; for(i=1; i<=k; i++) { scanf("%d %d",&x,&y); count[x][y]=-1; } scanf("%d %d",&startx,&starty); scanf("%d %d",&endx,&endy); if(startx==endx && starty==endy) { printf("0/n0/n"); continue; } flag1=0; l[0]=1; l[1]=0; que[flag1][0][0]=startx; que[flag1][0][1]=starty; count[startx][starty]=1; step=1; while(count[endx][endy]==0) { flag1=(step+1)%2; flag2=step%2; if(l[flag1]==0)break; for(i=0; i<l[flag1]; i++) { x=que[flag1][i][0]; y=que[flag1][i][1]; for(j=0; j<4; j++) { tx=x+dx[j]; ty=y+dy[j]; if(tx<1 || ty<1 || tx>n || ty>m) continue; if(count[tx][ty]==-1) continue; if(count[tx][ty]) { count[tx][ty]+=count[x][y]; continue; } else { que[flag2][l[flag2]][0]=tx; que[flag2][l[flag2]][1]=ty; l[flag2]++; count[tx][ty]+=count[x][y]; } } } step++; l[flag1]=0; } if(count[endx][endy]) printf("%d/n%d/n",step-1,count[endx][endy]); else printf("No Solution!/n"); } return 0; } #endif
