SPOJ-Grid ,水广搜easy bfs

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;

}