TIOJ 1022 H.跑跑卡恩車

[BFS]

/* LANG:CPP
** http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1022
** 2013-11-03
** BFS
*/
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<math.h>
#include<vector>
int table[101][101];
int dp[101][101];
int m,n;
struct point{
    int x,y;
    void Print()
    {
        printf("(%d,%d)\n",x,y);
    }
};
bool Check(int x,int y)
{
    return ((x>=1)&&(y>=1)&&(x<=m)&&(y<=n));
}
int main()
{
    point start;
    start.x=1;start.y=1;
    int T;scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d %d",&m,&n);
        for(int lx=1;lx<=m;lx++)
            for(int ly=1;ly<=n;ly++)
                scanf("%d",&table[lx][ly]);
        std::vector<point> in;      in.push_back(start);
        std::vector<point> out;     out.clear();
        dp[1][1]=1;
        point tmp;
        int step=1;
        while(in.size()&&(dp[m][n]==0))
        {
            //printf("step=%d\n",in.size());
            step++;
            for(int lx=0;lx<in.size();lx++)
            {

                int px=in[lx].x,py=in[lx].y;
                //printf("On(%d,%d)=%d\n",px,py,dp[px][py]);
                if(Check(px-1,py)&&(dp[px-1][py]==0)&&(abs(table[px][py]-table[px-1][py])<=5))
                {
                    tmp.x=px-1; tmp.y=py;
                    out.push_back(tmp);
                    dp[px-1][py]=step;
                    //tmp.Print();
                }
                if(Check(px+1,py)&&(dp[px+1][py]==0)&&(abs(table[px][py]-table[px+1][py])<=5))
                {
                    tmp.x=px+1; tmp.y=py;
                    out.push_back(tmp);
                    dp[px+1][py]=step;
                    //tmp.Print();
                }
                if(Check(px,py-1)&&(dp[px][py-1]==0)&&(abs(table[px][py-1]-table[px][py])<=5))
                {
                    tmp.x=px; tmp.y=py-1;
                    out.push_back(tmp);
                    dp[px][py-1]=step;
                    //tmp.Print();
                }
                if(Check(px,py+1)&&(dp[px][py+1]==0)&&(abs(table[px][py]-table[px][py+1])<=5))
                {
                    tmp.x=px; tmp.y=py+1;
                    out.push_back(tmp);
                    dp[px][py+1]=step;
                    //tmp.Print();
                }
            }
            in.clear();
            for(int lx=0;lx<out.size();lx++)
                in.push_back(out[lx]);
            out.clear();
            /*for(int lx=1;lx<=m;lx++)
            {
                for(int ly=1;ly<=n;ly++)
                    printf("%d ",dp[lx][ly]);
                printf("\n");
            }
            system("PAUSE");*/
        }

        printf("%d\n",dp[m][n]-1);
    }
    return 0;
}