学步园

题目不说了。。。

一共三个版本，first——也就是最长的是我写的。second版本当遍历20X20的空棋盘就要死了。。。

Astyle插件真好用。。。

什么？没听说过Astyle？呵呵，用code::blocks吧，很强大！gprof插件也很强大。

#define first</p> <p>#ifdef first<br /> #include<stdio.h><br /> #include<stdlib.h><br /> #define MAX_SIZE 100</p> <p>int row,col,room;<br /> int sx,sy,tx,ty;<br /> int maza[MAX_SIZE+1][MAX_SIZE+1];<br /> long path[MAX_SIZE+1][MAX_SIZE+1];</p> <p>/*---------queue.h begins-----------------*/<br /> typedef struct QueueNode<br /> {<br /> int x;<br /> int y;<br /> int depth;<br /> struct QueueNode* next;<br /> } qnode;</p> <p>typedef struct Queue<br /> {<br /> qnode* head;<br /> qnode* tail;<br /> } queue;</p> <p>int init(queue* q)<br /> {<br /> q->head=q->tail=NULL;<br /> return 0;<br /> }</p> <p>qnode* cnode(int x,int y,int depth)<br /> {<br /> qnode* node=(qnode*)malloc(sizeof(qnode));<br /> if(!node)<br /> puts("error!");<br /> else<br /> {<br /> node->x=x;<br /> node->y=y;<br /> node->depth=depth;<br /> }<br /> return node;<br /> }</p> <p>int enqueue(queue* q,int x,int y,int depth)<br /> {<br /> qnode* node=cnode(x,y,depth);<br /> if(q->head==NULL||q->tail==NULL)<br /> q->head=q->tail=node;<br /> else<br /> {<br /> q->tail->next=node;<br /> q->tail=node;<br /> }<br /> return 0;<br /> }</p> <p>int dequeue(queue* q,int*x ,int*y,int* depth)<br /> {<br /> if(!q->head||!q->tail)<br /> puts("Queue is currently empty!");<br /> if(q->head==q->tail)<br /> {<br /> *x=q->head->x;<br /> *y=q->head->y;<br /> *depth=q->head->depth;<br /> free(q->head);<br /> q->head=q->tail=NULL;<br /> }<br /> else<br /> {<br /> qnode* tmp=q->head;<br /> *x=tmp->x;<br /> *y=tmp->y;<br /> *depth=tmp->depth;<br /> q->head=tmp->next;<br /> free(tmp);<br /> }<br /> return 0;<br /> }</p> <p>int destroy(queue* q)<br /> {<br /> qnode* tmp;<br /> if(!q)<br /> puts("error in function destroy");<br /> while(q->head!=q->tail)<br /> {<br /> tmp=q->head;<br /> q->head=tmp->next;<br /> free(tmp);<br /> }<br /> free(q->head);<br /> free(q);<br /> return 0;<br /> }<br /> int clear(queue* q)<br /> {<br /> qnode* tmp;<br /> if(!q)<br /> puts("error in function destroy");<br /> while(q->head!=q->tail)<br /> {<br /> tmp=q->head;<br /> q->head=tmp->next;<br /> free(tmp);<br /> }<br /> free(q->head);<br /> q->head=q->tail=NULL;<br /> return 0;<br /> }</p> <p>int isEmpty(queue* q)<br /> {<br /> return q->head==NULL; /*q->tail==NULL is also ok!*/<br /> }</p> <p>/*----------------queue.h ends---------------------*/</p> <p>int main(void)<br /> {<br /> scanf("%d%d%d",&row,&col,&room);</p> <p> int i,j,k;<br /> for(i=0; i<room; i++)<br /> {<br /> scanf("%d%d",&j,&k);<br /> maza[j][k]=-1;<br /> }<br /> scanf("%d%d%d%d",&sx,&sy,&tx,&ty);</p> <p> queue* q=(queue*)malloc(sizeof(queue));<br /> init(q);</p> <p> enqueue(q,sx,sy,1);<br /> maza[sx][sy]=1;<br /> int x,y,depth,found=0;<br /> while(!isEmpty(q))<br /> {<br /> dequeue(q,&x,&y,&depth);<br /> if(x==tx&&y==ty)<br /> {<br /> found=1;<br /> break;<br /> }<br /> else<br /> {<br /> if(x-1>=1&&!maza[x-1][y])<br /> enqueue(q,x-1,y,depth+1),maza[x-1][y]=depth+1;<br /> if(x+1<=row&&!maza[x+1][y])<br /> enqueue(q,x+1,y,depth+1),maza[x+1][y]=depth+1;<br /> if(y-1>=1&&!maza[x][y-1])<br /> enqueue(q,x,y-1,depth+1),maza[x][y-1]=depth+1;<br /> if(y+1<=col&&!maza[x][y+1])<br /> enqueue(q,x,y+1,depth+1),maza[x][y+1]=depth+1;<br /> }<br /> }<br /> clear(q);</p> <p> path[sx][sy]=1;<br /> enqueue(q,sx,sy,1);<br /> while(!isEmpty(q))<br /> {<br /> dequeue(q,&x,&y,&depth);<br /> if(x-1>=1&&maza[x-1][y]==depth+1)<br /> {<br /> if(!path[x-1][y])<br /> enqueue(q,x-1,y,depth+1);<br /> path[x-1][y]+=path[x][y];<br /> }<br /> if(x+1<=row&&maza[x+1][y]==depth+1)<br /> {<br /> if(!path[x+1][y])<br /> enqueue(q,x+1,y,depth+1);<br /> path[x+1][y]+=path[x][y];<br /> }<br /> if(y-1>=1&&maza[x][y-1]==depth+1)<br /> {<br /> if(!path[x][y-1])<br /> enqueue(q,x,y-1,depth+1);<br /> path[x][y-1]+=path[x][y];<br /> }<br /> if(y+1<=col&&maza[x][y+1]==depth+1)<br /> {<br /> if(!path[x][y+1])<br /> enqueue(q,x,y+1,depth+1);<br /> path[x][y+1]+=path[x][y];<br /> }<br /> }<br /> destroy(q);</p> <p> if(!found)<br /> puts("No Solution!");<br /> else<br /> printf("%d/n%ld/n",depth-2,path[tx][ty]);</p> <p> return 0;<br /> }<br /> #endif</p> <p>#ifdef second</p> <p>#include<stdio.h><br /> #define N 100<br /> int s,map[N+1][N+1];<br /> typedef struct<br /> {<br /> int x,y;<br /> } xy;<br /> xy queue[N*N],start,end,last;</p> <p>void depth(int x,int y)<br /> {<br /> if(map[x][y]==1)<br /> {<br /> s++;<br /> x=last.x;<br /> x=last.y;<br /> return;<br /> }<br /> last.x=x;<br /> last.y=y;<br /> if(x==1&&y==1)<br /> return;<br /> if(map[x-1][y]==map[x][y]-1)<br /> depth(x-1,y);<br /> if(map[x+1][y]==map[x][y]-1)<br /> depth(x+1,y);<br /> if(map[x][y-1]==map[x][y]-1)<br /> depth(x,y-1);<br /> if(map[x][y+1]==map[x][y]-1)<br /> depth(x,y+1);<br /> }</p> <p>int main()<br /> {<br /> int front=0,rear=1;<br /> int n,m,k,i,j;<br /> scanf("%d%d%d",&n,&m,&k);<br /> for(i=0; i<=N; i++)<br /> for(j=0; j<=N; j++)<br /> map[i][j]=0;<br /> while(k--)<br /> {<br /> scanf("%d%d",&i,&j);<br /> map[i][j]=-1;<br /> }<br /> scanf("%d%d",&start.x,&start.y);<br /> scanf("%d%d",&end.x,&end.y);<br /> queue[front].x=start.x;<br /> queue[front].y=start.y;<br /> map[start.x][start.y]=1;<br /> while(front<rear)<br /> {<br /> i=queue[front].x;<br /> j=queue[front].y;<br /> if(i==end.x&&j==end.y)<br /> break;<br /> if(i-1>0&&map[i-1][j]==0)<br /> {<br /> map[i-1][j]=map[i][j]+1;<br /> queue[rear].x=i-1;<br /> queue[rear].y=j;<br /> rear++;<br /> }<br /> if(j-1>0&&map[i][j-1]==0)<br /> {<br /> map[i][j-1]=map[i][j]+1;<br /> queue[rear].x=i;<br /> queue[rear].y=j-1;<br /> rear++;<br /> }<br /> if(i+1<=n&&map[i+1][j]==0)<br /> {<br /> map[i+1][j]=map[i][j]+1;<br /> queue[rear].x=i+1;<br /> queue[rear].y=j;<br /> rear++;<br /> }<br /> if(j+1<=m&&map[i][j+1]==0)<br /> {<br /> map[i][j+1]=map[i][j]+1;<br /> queue[rear].x=i;<br /> queue[rear].y=j+1;<br /> rear++;<br /> }<br /> front++;<br /> }<br /> if(front==rear)<br /> printf("No Solution!/n");<br /> else<br /> {<br /> s=0;<br /> last.x=i;<br /> last.y=j;<br /> printf("%d/n",map[i][j]-1);<br /> depth(i,j);<br /> printf("%d/n",s);<br /> }<br /> return 0;<br /> }<br /> #endif</p> <p>#ifdef third<br /> #include <stdio.h><br /> int count[1001][1001];<br /> int que[2][1000000][2];<br /> int main(void)<br /> {<br /> int n,m,k;<br /> int i,j,x,y,startx,starty,endx,endy,step,flag1,flag2,l[2],tx,ty;<br /> int dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1};<br /> while(scanf("%d %d %d",&n,&m,&k)!=EOF)<br /> {<br /> for(i=1; i<=n; i++)<br /> for(j=1; j<=m; j++)<br /> count[i][j]=0;<br /> for(i=1; i<=k; i++)<br /> {<br /> scanf("%d %d",&x,&y);<br /> count[x][y]=-1;<br /> }<br /> scanf("%d %d",&startx,&starty);<br /> scanf("%d %d",&endx,&endy);<br /> if(startx==endx && starty==endy)<br /> {<br /> printf("0/n0/n");<br /> continue;<br /> }<br /> flag1=0;<br /> l[0]=1;<br /> l[1]=0;<br /> que[flag1][0][0]=startx;<br /> que[flag1][0][1]=starty;<br /> count[startx][starty]=1;<br /> step=1;<br /> while(count[endx][endy]==0)<br /> {<br /> flag1=(step+1)%2;<br /> flag2=step%2;<br /> if(l[flag1]==0)break;<br /> for(i=0; i<l[flag1]; i++)<br /> {<br /> x=que[flag1][i][0];<br /> y=que[flag1][i][1];<br /> for(j=0; j<4; j++)<br /> {<br /> tx=x+dx[j];<br /> ty=y+dy[j];<br /> if(tx<1 || ty<1 || tx>n || ty>m)<br /> continue;<br /> if(count[tx][ty]==-1)<br /> continue;<br /> if(count[tx][ty])<br /> {<br /> count[tx][ty]+=count[x][y];<br /> continue;<br /> }<br /> else<br /> {<br /> que[flag2][l[flag2]][0]=tx;<br /> que[flag2][l[flag2]][1]=ty;<br /> l[flag2]++;<br /> count[tx][ty]+=count[x][y];<br /> }<br /> }<br /> }<br /> step++;<br /> l[flag1]=0;<br /> }<br /> if(count[endx][endy])<br /> printf("%d/n%d/n",step-1,count[endx][endy]);<br /> else<br /> printf("No Solution!/n");<br /> }<br /> return 0;<br /> }<br /> #endif<br />