FOJ 1205

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（移动次数）时有多少种不同的最短路径。

  1 #include<stdio.h>
  2 #include<string.h>
  3 int sx[4]={0,1,0,-1};
  4 int sy[4]={1,0,-1,0};
  5 int map[100][100];
  6 int mark[100][100];
  7 int n,m;
  8 int x1,y1,x2,y2;
  9 int min_step,sum_min;
 10 int que[10000][2];
 11 int que_step[10000];
 12 void bfs(int h,int l)
 13 {
 14     
 15     int front,rear;
 16     front=rear=0;
 17     que[rear][0]=h;
 18     que[rear][1]=l;
 19     rear++;
 20     map[h][l]=1;
 21     que_step[front]=0;
 22     int xx,yy,i;
 23     
 24     while(front<rear)
 25     {
 26         for(i=0;i<4;i++)
 27         {
 28             xx=que[front][0]+sx[i];
 29             yy=que[front][1]+sy[i];
 30             
 31             if(xx==x2&&yy==y2)
 32             {
 33                 min_step=que_step[front]+1;
 34                 return;
 35             }
 36             if(map[xx][yy]==0&&xx<=n&&xx>=1&&yy>=1&&yy<=m)
 37             {
 38                 //printf("(%d %d) step=%d
",xx,yy,que_step[front]+1);
 39                 que[rear][0]=xx;
 40                 que[rear][1]=yy;
 41                 que_step[rear]=que_step[front]+1;
 42                 rear++;
 43                 map[xx][yy]=1;
 44                 
 45             }
 46         }
 47         front++;
 48     }
 49 }
 50 int t;
 51 void dfs(int x,int y,int c_step)
 52 {
 53     //printf("%d
",c_step);
 54     if(x==x2&&y==y2&&c_step==min_step)
 55     {
 56         
 57         sum_min++; return ;
 58     }
 59     if((x>x2?x-x2:x2-x)+(y>y2?y-y2:y2-y)+c_step>min_step) return ;
 60     int i;
 61     for(i=0;i<4;i++)
 62     {
 63         int xx,yy;
 64         xx=x+sx[i];
 65         yy=y+sy[i];
 66         if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mark[xx][yy]==0)
 67         {
 68             mark[xx][yy]=1;
 69             dfs(xx,yy,c_step+1);
 70             mark[xx][yy]=0;
 71         }
 72     }
 73     
 74 }
 75 int main()
 76 {
 77     int k,i,j;
 78     while(scanf("%d %d %d",&n,&m,&k)!=EOF)
 79     {
 80         min_step=-1;sum_min=0;
 81         for(i=1;i<=n;i++)
 82         {
 83             memset(map[i],0,sizeof(map[i]));
 84             memset(mark[i],0,sizeof(mark[i]));
 85         }
 86         for(i=1;i<=k;i++)
 87         {
 88             int a,b;
 89             scanf("%d %d",&a,&b);
 90             map[a][b]=1;
 91             mark[a][b]=1;
 92         }
 93         scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
 94         t=1;
 95         bfs(x1,y1);
 96         
 97         if(min_step==-1)
 98             printf("No Solution!
");
 99         else
100         {
101             dfs(x1,y1,0);
102             printf("%d
%d
",min_step,sum_min);
103         }
104     }
105     return 0;
106 }
107 
108 /*
109 
110 3 3 1
111 2 2
112 1 1
113 3 3
114 
115 */

View Code