题目
Description
由M行N列的方格构成一个迷宫,相邻方格之间可能是相通的,也可能有隔墙,各方格位置由对应坐标确定。在(1,1)处由入口,在(M,N)处有一个出口,在入口和出口之间有路相通,求从入口到出口的最短路径,若无法到达,输出“-1”
Input
第1行有两个整数,M,N(2<=M,N<=10), 接下来是M*N的0,1矩阵 0表示通路,1表示墙(数据保证入口和出口为通路)。
Output
输出最短路径
Sample Input
6 8
0 0 1 0 0 0 1 1
1 0 0 0 1 0 0 0
0 0 0 1 1 0 1 1
1 1 0 1 0 0 0 0
0 0 0 0 0 1 0 1
1 0 1 0 0 0 0 0Sample Output
12
题解
最短路问题,使用BFS求解即可
代码
/* By:OhYee Github:OhYee Blog:http://www.oyohyee.com/ Email:oyohyee@oyohyee.com かしこいかわいい? エリーチカ! 要写出来Хорошо的代码哦~ */ #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <vector> #include <list> #include <queue> #include <stack> #include <map> #include <set> #include <functional> using namespace std; const int maxn = 105; const int delta[] = {-1,1,0,0}; int Map[maxn][maxn]; bool vis[maxn][maxn]; int dis[maxn][maxn]; bool Do() { int m,n; if(scanf("%d%d",&n,&m)==EOF) return false; for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) scanf("%d",&Map[i][j]); memset(vis,false,sizeof(vis)); queue<pair<int,int> > Q; vis[1][1] = true; Q.push(pair<int,int>(1,1)); dis[1][1] = 0; dis[n][m] = -1; while(!Q.empty()) { int x = Q.front().first; int y = Q.front().second; Q.pop(); if(x == n && y == m) break; for(int i = 0;i < 4;i++) { int xx = x + delta[i]; int yy = y + delta[3 - i]; if(!(xx >= 1 && x <= n&&yy >= 1 && yy <= m)) continue; if(vis[xx][yy]) continue; if(Map[xx][yy]) continue; vis[xx][yy] = true; dis[xx][yy] = dis[x][y] + 1; Q.push(pair<int,int>(xx,yy)); } } printf("%d\n",dis[n][m]); return true; } int main() { while(Do()); return 0; }