SPOJ - SERGRID 【最短路】

You are on an nxm grid where each square on the grid has a digit on it. From a given square that has digit k on it, a Move consists of jumping exactly k squares in one of the four cardinal directions. A move cannot go beyond the edges of the grid; it does not wrap. What is the minimum number of moves required to get from the top-left corner to the bottom-right corner?

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains two space-separated integers n and m (1≤n,m≤500), indicating the size of the grid. It is guaranteed that at least one of n and m is greater than 1. The next n lines will each consist of m digits, with no spaces, indicating the nxm grid. Each digit is between 0 and 9, inclusive. The top-left corner of the grid will be the square corresponding to the first character in the first line of the test case. The bottom-right corner of the grid will be the square corresponding to the last character in the last line of the test case.

Output

Output a single integer on a line by itself representing the minimum number of moves required to get from the top-left corner of the grid to the bottom-right. If it isn’t possible, output -1.

Example

Input: 5 4 2120 1203 3113 1120 1110 Output: 6

题目大意：

给你一个N*M大小的迷宫，从左上角走到右下角，每一步都必须走格子上数字的长度，要求不能转弯，问最少几步能够到达右下角。

思路：

水一发，可以Bfs搞，我建了图跑最短路~~~~~~~

Ac代码：

#include<stdio.h> #include<string.h> #include<queue> #include<vector> using namespace std; char a[505][505]; int num[505][505]; int fx[4]={0,0,1,-1}; int fy[4]={1,-1,0,0}; vector<int >mp[505*505]; int dis[505*505]; int vis[505*505]; void SPFA(int n) { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { dis[i]=0x3f3f3f3f; if(i==1)dis[i]=0; } queue<int>s; s.push(1); while(!s.empty()) { int u=s.front(); vis[u]=0; s.pop(); for(int i=0;i<mp[u].size();i++) { int v=mp[u][i]; if(dis[v]>dis[u]+1) { dis[v]=dis[u]+1; if(vis[v]==0) { vis[v]=1; s.push(v); } } } } } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) { scanf("%s",a[i]); } int cnt=1; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { num[i][j]=cnt++; } } for(int i=1;i<=cnt;i++)mp[i].clear(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { for(int z=0;z<4;z++) { int vi=i+fx[z]*(a[i][j]-'0'); int vj=j+fy[z]*(a[i][j]-'0'); if(vi>=0&&vi<n&&vj>=0&&vj<m) { mp[num[i][j]].push_back(num[vi][vj]); } } } } SPFA(cnt-1); if(dis[num[n-1][m-1]]==0x3f3f3f3f)printf("-1\n"); else printf("%d\n",dis[num[n-1][m-1]]); } }