Description 小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这 m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。 对于给定的小鼠的迷宫，编程计算小鼠a通向小鼠b的所有最短道路。 Input 第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。 Output 输出小鼠a通向小鼠b的最短路长度和有多少条不同的最短路。 第一行是最短路长度,第2行是不同的最短路数。 如果小鼠a无法通向小鼠b则输出“No Solution!”。 Sample Input 8 8 3 3 3 4 5 6 6 2 1 7 7 Sample Output 11 96 Source Fujian OI -- 2005 #include #include #include #define MAX 8000 struct Position{ int row; int col; }; typedef struct Position position; struct Queue{ position queue[MAX]; int top; int rear; }; typedef struct Queue q; position start,end; int num=0; position offset[4]; int grid[MAX][MAX]; void init_q(q *p) { p->top=-1; p->rear=-1; } void enqueue(q *p,position x) { p->rear++; p->queue[p->rear].col=x.col; p->queue[p->rear].row=x.row; } position delq(q *p) { p->top++; return p->queue[p->top]; } void fun(position nbr) { int i; position here; here.col=nbr.col; here.row=nbr.row; for(i=0;i<4;i++) { nbr.row=here.row+offset[i].row; nbr.col=here.col+offset[i].col; if(grid[nbr.row][nbr.col]==grid[here.row][here.col]-1) { if(grid[nbr.row][nbr.col]==2) { num++; return ; } else fun(nbr); } } } int main() { int flag,len,flag1; position here,nbr; q *p; int m,n,k,px,py,i; while(scanf("%d%d%d",&n,&m,&k)==3) { num=0; flag=0; flag1=0; p=(q*)malloc(sizeof(q)); memset(grid,0,sizeof(int)*800*800); init_q(p); for(i=0;i<=m+1;i++) grid[0][i]=grid[n+1][i]=1; for(i=0;i<=n+1;i++) grid[i][0]=grid[i][m+1]=1; for(i=0;itop==p->rear) break; else { nbr=delq(p); continue; } } if(p->top==p->rear) { printf("No Solution!\n"); flag1=1; break; } nbr=delq(p); }while(1); if(flag1==0) { printf("%d\n",len-2); grid[end.row][end.col]=len; fun(end); printf("%d\n",num); } } return 0; }

评论