SERGRID - Grid
一个水广搜我竟然纠结了这么久，三天不练手生啊，况且我快三个月没练过搜索了。。。
题意：n*m的方格，每个格子有一个数，意味着在此方格上你可以上下左右移动s[x][y]个格子，不能出界。求左上角那个格子到右下角那个格子最少需要走几步。
思路：就是一个队列广搜，开始做一时想不起要用队列，结果用dfs左改右改，还不容易调出来了结果TLE了，我知道清楚标记的话复杂度最高500^4，不T才怪。后来叫队友看了看队友说这不就是水广搜嘛，然后水之。他说的倒是提醒了我，用广搜标记，怎么标记呢，用一个二维数组表示左上角到每个格子最少步数，然后初始化为INF，这样就每次将能到达的几个点加入队列就行了，复杂度O(n)。水之。
这么水的搜索我竟然纠结了近2小时，细思恐极。
const int N=500+10; char s[N][N]; int w[N][N],n,m; struct node { int x,y; } Node; void bfs(int x,int y) { queue<node>q; Node.x=x,Node.y=y; q.push(Node); while(!q.empty()) { node tmp=q.front(); q.pop(); int xx=tmp.x,yy=tmp.y; if(tmp.x==n-1&&tmp.y==m-1) break; // printf("%d %d\n",tmp.x,tmp.y); int x1=xx-(s[xx][yy]-'0'),y1=yy-(s[xx][yy]-'0'); int x2=xx+(s[xx][yy]-'0'),y2=yy+(s[xx][yy]-'0'); // printf("x1=%d x2=%d y1=%d y2=%d %d\n",x1,x2,y1,y2,s[tmp.x][tmp.y]-'0'); if(x1>=0&&x1<n&&w[x1][yy]==INF)//ио { w[x1][yy]=w[xx][yy]+1; Node.x=x1,Node.y=yy; q.push(Node); } if(x2>=0&&x2<n&&w[x2][yy]==INF)//об { w[x2][yy]=w[xx][yy]+1; Node.x=x2,Node.y=yy; q.push(Node); } if(y1>=0&&y1<m&&w[xx][y1]==INF)//вС { w[xx][y1]=w[xx][yy]+1; Node.x=xx,Node.y=y1; q.push(Node); } if(y2>=0&&y2<m&&w[xx][y2]==INF)//ср { w[xx][y2]=w[xx][yy]+1; Node.x=xx,Node.y=y2; q.push(Node); } } } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=0; i<N; i++) for(int j=0; j<N; j++) w[i][j]=INF; for(int i=0; i<n; i++) scanf("%s",s[i]); w[0][0]=0; bfs(0,0); if(w[n-1][m-1]==INF) printf("-1\n"); else printf("%d\n",w[n-1][m-1]); } return 0; }
