Mutual Training for Wannafly Union #6Grid SPOJ - SERGRID A - Grid（bfs）

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 代码 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<ctype.h> #include<math.h> #include<stack> #include<queue> #include<map> #include<set> #include<vector> #include<string> #include<iostream> #include<algorithm> #include<utility> typedef long long ll; const double Pi = acos(-1.0); const int N = 1e6+10, M = 1e3+20, mod = 1e9+7, inf = 2e9+10; const double e=2.718281828459 ; const double esp=1e-9; using namespace std; int n,m; char maze[M][M]; int vis[M][M]; struct node { int x,y; int step; }; void bfs() { memset(vis,0,sizeof(vis)); queue<node>q; node a,b; a.x=0; a.y=0; a.step=0; vis[a.x][a.y]=1; q.push(a); while(!q.empty()) { a=q.front(); q.pop(); int mm=maze[a.x][a.y]-'0'; if(a.x==n-1&&a.y==m-1) { printf("%d\n",a.step); return ; } for(int i=0;i<4;i++) { int xx,yy; if(i==0) {xx=a.x-mm; yy=a.y; } else if(i==1) {xx=a.x; yy=a.y+mm; } else if(i==2) { xx=a.x+mm;yy=a.y;} else {xx=a.x;yy=a.y-mm;} if(xx>=0&&xx<n&&yy>=0&&yy<m&&vis[xx][yy]==0) { b.x=xx; b.y=yy; vis[xx][yy]=1; b.step=a.step+1; q.push(b); } } } printf("-1\n"); } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) { scanf("%s",maze[i]); } bfs(); } return 0; }