Problem 1205 小鼠迷宫问题

方法二的原作者：https://blog.csdn.net/mengxiang000000/article/details/50850996

Accept: 680    Submit: 2305
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

估计你百分百卡在了TLE上。做了老长时间了，都快疯了。看了大佬的代码。总结出了两种方式。

首先，超时的原因就是在dfs上。想到剪枝了，但是没什么能剪掉的对吧。这里就可以用大神的方法二变换一种思路来“剪枝”

方法一：

这种方也很巧妙，知识一个小技巧，会让你的dfs少走很多弯路(大佬们的思维岂能是你我所能匹敌。。。。)

在dfs中steps是当前的步数，那么如果此时的位置x,y与(到)终点ex,ey的距离(步数)加上steps大于最小步数了，肯定就不会走这条路了。也是一种剪枝的方法

 方法二：

建立一个step的步数数组。在dfs时，不像我们一开始的思路，找到了最短路就把他返回，而是把step填满（这里可能说的不是很准确，希望你们能理解。。。不删言语啊T-T）。然后再返回。这时候是不是想到了什么？

没错，我们去dfs这个step数组，而且还是凶ex,ey开始往回搜索。为啥呢？

因为，在bfs时，每次走一个点标记一下，那么这个点标记的这个值一定是到这个点的最小步数。当我们都标记玩时。我们从终点开始向起点dfs，只要是dfs的下一个点的标记值-1等于此时这个点，说明就能从那个点走到当前的点。不断的搜索下去，如若那个点等于开始点了。那么路径条数就+1；ok了。

/*-------------方法一-----------------*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include <sstream>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
#define maxsize 1005int n,m,k;
int sx,sy,ex,ey;    //开始和结束坐标
int vis[maxsize][maxsize];
int hinder[maxsize][maxsize];
int d[][2]={0,1,1,0,0,-1,-1,0};
int cnt,ans;struct Room{int x,y,step;
};bool check(int x,int y){if(x>=1 && x<=n && y>=1 && y<=m){return true;}return false;
}int bfs(struct Room r){if(!check(r.x,r.y)) return 0;if(hinder[r.x][r.y]!=0 || vis[r.x][r.y]!=0) return 0;if(r.x==ex && r.y==ey){return r.step;}queue<struct Room> que;que.push(r);vis[r.x][r.y]=1;while(!que.empty()){struct Room t = que.front();que.pop();vis[t.x][t.y] = 1;if(t.x==ex && t.y==ey){return t.step;}struct Room p;for(int i=0;i<4;i++){p.x = d[i][0]+t.x;p.y = d[i][1]+t.y;p.step = t.step+1;if(check(p.x,p.y) && vis[p.x][p.y]==0 && hinder[p.x][p.y]==0){que.push(p);vis[p.x][p.y]=1;}}}
}void dfs(int x,int y,int steps){if(!check(x,y)) return ;if(vis[x][y]!=0 || hinder[x][y]!=0) return ;if(x==ex && y==ey && steps==ans){cnt++;return ;}if(steps>ans) return ;if(abs(x-ex)+abs(y-ey)+steps>ans) return;vis[x][y] = 1;for(int i=0;i<4;i++){int a = x+d[i][0];int b = y+d[i][1];if(check(a,b) && vis[a][b]==0 && hinder[a][b]==0){dfs(a,b,steps+1);vis[a][b] = 0;}}return ;
}int main(){while(scanf("%d%d%d",&n,&m,&k)!=EOF){cnt = 0;ans = 0;memset(vis,0,sizeof(vis));memset(hinder,0,sizeof(hinder));int a,b;for(int i=0;i<k;i++){scanf("%d%d",&a,&b);hinder[a][b]=1;}scanf("%d%d%d%d",&sx,&sy,&ex,&ey);struct Room r;r.x = sx;r.y = sy;r.step = 0;ans = bfs(r);if(ans!=0) cout<<ans<<endl;else cout<<"No Solution!"<<endl;if(ans!=0){memset(vis,0,sizeof(vis));dfs(sx,sy,0);cout<<cnt<<endl;}}
}

/*-----------------方法二--------------------*/#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct zuobiao
{int x,y;
}now,nex;
int step[105][105];
int a[105][105];
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
int n,m,k;
int sx,sy,ex,ey;
int cont;
void bfs(int x,int y)
{memset(step,0,sizeof(step));step[x][y]=1;now.x=x;now.y=y;queue<zuobiao >s;s.push(now);while(!s.empty()){now=s.front();s.pop();for(int i=0;i<4;i++){nex.x=now.x+fx[i];nex.y=now.y+fy[i];if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&step[nex.x][nex.y]==0&&a[nex.x][nex.y]!=1){step[nex.x][nex.y]=step[now.x][now.y]+1;s.push(nex);}}}
}
void dfs(int x,int y)
{if(x==sx&&y==sy){cont++;return ;}else{for(int i=0;i<4;i++){int xx=x+fx[i];int yy=y+fy[i];if(step[xx][yy]==step[x][y]-1){dfs(xx,yy);}}}
}
int main()
{while(~scanf("%d%d%d",&n,&m,&k)){cont=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){a[i][j]=0;}}while(k--){int x,y;scanf("%d%d",&x,&y);x--;y--;a[x][y]=1;}scanf("%d%d%d%d",&sx,&sy,&ex,&ey);sx--;sy--;ex--;ey--;bfs(sx,sy);printf("%d\n",step[ex][ey]-1);dfs(ex,ey);printf("%d\n",cont);}
}