hdu 1254

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1254

题意：中文。

mark：BFS+DFS。用BFS来展开箱子的位置和小人的位置，每个节点有2个属性，1是箱子所在位置的坐标，二是一个hash值来表示小人能位于箱子上下左右四个地方的情况（每个方向能否到达用1位来表示，共需要用15）。计算hash值的时候用DFS来穷举小人所有能到达的位置。

wa了1次，DFS的时候忘记考虑小人不能穿过箱子的情况。

代码：

# include <stdio.h>
# include <string.h>


int graph[10][10] ;
int n, m ;
int sx, sy, ex, ey, rx, ry ;
int vis[10][10][20], vv[10][10] ;
int q[10*10*20][3] ;
int dr[4][2] = {-1,0,1,0,0,-1,0,1} ; //up down left right
int tab[4][2] = {1,0,-1,0,0,1,0,-1} ;


int test (int x, int y)
{
    if (x < 0 || x >= n) return 0 ;
    if (y < 0 || y >= m) return 0 ;
    if (graph[x][y] == 1) return 0 ;
    return 1 ;
}


void dfs (int x, int y)
{
    int i, xx, yy ;
    vv[x][y] = 1 ;
    for (i = 0 ; i < 4 ; i++)
    {
        xx = x + tab[i][0] ;
        yy = y + tab[i][1] ;
        if (test(xx, yy) == 0) continue ;
        if (graph[xx][yy] == 1) continue ;
        if (vv[xx][yy]==1) continue ;
        dfs(xx, yy) ;
    }
}


int hash(int x1, int y1, int x2, int y2)
{
    int i, xx, yy, val = 0 ;
    memset (vv, 0, sizeof(vv)) ;
    vv[x1][y1] = 1 ;
    dfs (x2, y2) ;
    for (i = 0 ; i < 4 ; i++)
    {
        xx = x1 + tab[i][0] ;
        yy = y1 + tab[i][1] ;
        if (test(xx, yy) == 0) continue ;
        val += (vv[xx][yy]<<i) ;
    }
    return val ;
}


int bfs()
{
    int i, front = 0, rear = 1 ;
    int x, y, h = hash(sx, sy, rx, ry) ;
    int xx, yy, hh ;
    memset (vis, -1, sizeof(vis)) ;
    q[0][0] = sx, q[0][1] = sy, q[0][2] = h ;
    vis[sx][sy][h] = 0 ;
    
    while (front != rear)
    {
        x = q[front][0], y = q[front][1], h = q[front][2] ;
//        printf ("%d, %d, %d\n", x, y, vis[x][y][h]) ;
        front++ ;
        if (x == ex && y == ey) return vis[x][y][h] ;
        for (i = 0 ; i < 4 ; i++)
        {
            if (!test(x+dr[i][0], y+dr[i][1])) continue ;
            if (!test(x+tab[i][0], y+tab[i][1])) continue ;
            if (((h>>i)&1) == 0) continue ;
            xx = x + dr[i][0], yy = y + dr[i][1] ;
            hh = hash(xx, yy, x, y) ;
            if (vis[xx][yy][hh] != -1) continue ;
            q[rear][0] = xx, q[rear][1] = yy, q[rear][2] = hh ;
            rear++ ;
            vis[xx][yy][hh] = vis[x][y][h] + 1 ;
        }
    }
    return -1 ;
}


int main ()
{
    int T, i, j ;
    scanf ("%d%*c", &T) ;
    while (T--)
    {
        scanf ("%d %d%*c", &n, &m) ;
        for (i = 0 ; i < n ; i++)
            for (j = 0 ; j < m ; j++)
            {
                scanf ("%d%*c", &graph[i][j]) ;
                if (graph[i][j] == 2) sx = i, sy = j ;
                if (graph[i][j] == 3) ex = i, ey = j ;
                if (graph[i][j] == 4) rx = i, ry = j ;
            }
        printf ("%d\n", bfs()) ;
    }
    return 0 ;
}