FOJ 1205

时间：2024-01-19 09:37:20

Problem 1205 小鼠迷宫问题

Accept: 522    Submit: 1679 Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

问题描述 小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。

小鼠的迷宫

编程任务

对于给定的小鼠的迷宫，编程计算小鼠a通向小鼠b的所有最短道路。

Input

本题有多组输入数据，你必须处理到EOF为止。 每组数据的第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。(1≤p,r≤n; 1≤q,s≤m)

结果输出

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

FJOI2005

利用bfs可以计算出最短路径的距离len（即移动次数），然后用dfs计算出等于len（移动次数）时有多少种不同的最短路径。
 #include<stdio.h>

 #include<string.h>

 int sx[]={,,,-};

 int sy[]={,,-,};

 int map[][];

 int mark[][];

 int n,m;

 int x1,y1,x2,y2;

 int min_step,sum_min;

 int que[][];

 int que_step[];

 void bfs(int h,int l)

 {

     int front,rear;

     front=rear=;

     que[rear][]=h;

     que[rear][]=l;

     rear++;

     map[h][l]=;

     que_step[front]=;

     int xx,yy,i;

     while(front<rear)

     {

         for(i=;i<;i++)

         {

             xx=que[front][]+sx[i];

             yy=que[front][]+sy[i];

             if(xx==x2&&yy==y2)

             {

                 min_step=que_step[front]+;

                 return;

             }

             if(map[xx][yy]==&&xx<=n&&xx>=&&yy>=&&yy<=m)

             {

                 //printf("(%d %d) step=%d\n",xx,yy,que_step[front]+1);

                 que[rear][]=xx;

                 que[rear][]=yy;

                 que_step[rear]=que_step[front]+;

                 rear++;

                 map[xx][yy]=;

             }

         }

         front++;

     }

 }

 int t;

 void dfs(int x,int y,int c_step)

 {

     //printf("%d\n",c_step);

     if(x==x2&&y==y2&&c_step==min_step)

     {

         sum_min++; return ;

     }

     if((x>x2?x-x2:x2-x)+(y>y2?y-y2:y2-y)+c_step>min_step) return ;

     int i;

     for(i=;i<;i++)

     {

         int xx,yy;

         xx=x+sx[i];

         yy=y+sy[i];

         if(xx>=&&xx<=n&&yy>=&&yy<=m&&mark[xx][yy]==)

         {

             mark[xx][yy]=;

             dfs(xx,yy,c_step+);

             mark[xx][yy]=;

         }

     }

 }

 int main()

 {

     int k,i,j;

     while(scanf("%d %d %d",&n,&m,&k)!=EOF)

     {

         min_step=-;sum_min=;

         for(i=;i<=n;i++)

         {

             memset(map[i],,sizeof(map[i]));

             memset(mark[i],,sizeof(mark[i]));

         }

         for(i=;i<=k;i++)

         {

             int a,b;

             scanf("%d %d",&a,&b);

             map[a][b]=;

             mark[a][b]=;

         }

         scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

         t=;

         bfs(x1,y1);

         if(min_step==-)

             printf("No Solution!\n");

         else

         {

             dfs(x1,y1,);

             printf("%d\n%d\n",min_step,sum_min);

         }

     }

     return ;

 }

 /*

 3 3 1

 2 2

 1 1

 3 3

 */

相关文章