Nightmare

3
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4 
1 0 0 0 1 0 0 1 
1 4 1 0 1 1 0 1 
1 0 0 0 0 3 0 1 
1 1 4 1 1 1 1 1 

4
-1
13

代码：

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

struct node
{
    int x,y;
    int t;
    int step;
    node(int a,int b,int c,int d):x(a),y(b),t(c),step(d) {}
    void Set(int a,int b,int c,int d)
    {
        x=a;
        y=b;
        t=c;
        step=d;
    }
};

int n,m;
int xs,ys,xe,ye;
int mat[10][10];
int vis[10][10];
int dir[4][2]= {-1,0,1,0,0,-1,0,1}; //up down left right

void bfs()
{
    memset(vis,0,sizeof(vis));
    queue<node> Q;
    node first=node(xs,ys,6,0);
    if(first.x==xe&&first.y==ye&&first.t>0)
    {
        printf("%d\n",first.step);
        return;
    }
    Q.push(first);
    vis[first.x][first.y]=first.t;
    while(!Q.empty())
    {
        //printf("----------------\n");
        first=Q.front();
        Q.pop();
        node next=node(0,0,0,0);
        for(int i=0; i<4; i++)
        {
            int tx=first.x+dir[i][0];
            int ty=first.y+dir[i][1];
            if(tx>=n||tx<0||ty>=m||ty<0)
                continue;
            if(mat[tx][ty]==0)
                continue;
            if(vis[tx][ty]+1>=vis[first.x][first.y])
                continue;
            next.Set(tx,ty,first.t-1,first.step+1);
            if(mat[tx][ty]==4)
                next.t=6;
            vis[next.x][next.y]=next.t;
            //printf("%d %d %d %d\n",next.x,next.y,next.t,next.step);
            if(next.x==xe&&next.y==ye&&next.t>0)
            {
                printf("%d\n",next.step);
                return;
            }
            Q.push(next);
        }
    }
    printf("-1\n");
}

int main()
{
    int t;
    scanf("%d",&t);
    //printf("%d\n",t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                scanf("%d",&mat[i][j]);
                if(mat[i][j]==2)
                {
                    xs=i;
                    ys=j;
                }
                if(mat[i][j]==3)
                {
                    xe=i;
                    ye=j;
                }
            }
        }
        bfs();
    }
    return 0;
}

HDU 1072 Nightmare（BFS）

原文：http://blog.csdn.net/xky1306102chenhong/article/details/50704958