SPOJ-SERGRID
n×m(1≤n,m≤500)个格子，每个格子有一个数字k，在格子上可向上下左右四个方向移动k步，但不能越界，问到右下脚需要几步
bfs即可
#include <cstdio> #include <queue> using namespace std; const int maxn=507; char pic[maxn][maxn]; int dis[maxn][maxn]; int n,m; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; typedef pair<int,int> P; queue<P> q; int bfs() { q.push(P(1,1)); P fr; dis[1][1]=1; while(!q.empty()) { fr=q.front(); q.pop(); int rr=fr.first,cc=fr.second; int k=pic[rr][cc]-'0'; if(k) for(int dd=0;dd<4;dd++) { int ddx=dx[dd]*k+rr,ddy=dy[dd]*k+cc; if(ddx>0&&ddx<n+1&&ddy>0&&ddy<m+1&&!dis[ddx][ddy]) { dis[ddx][ddy]=dis[rr][cc]+1; q.push(P(ddx,ddy)); if(ddx==n&&ddy==m) return dis[ddx][ddy]-1; } } } return -1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",pic[i]+1); printf("%d\n",bfs()); }