推箱子的题目，需要记录四个状态量，b[pi][pj][bi][bj]代表人和箱子在某种状态下所需要推动的最小step。
lev是无用记录量，仅作测试使用。
#include <cstdio>#include <string>int dir[4][2] =
...{
...{ 0, 1 }, ...{ 1, 0 }, ...{ - 1, 0 }, ...{ 0, -1 }
};int N, M, a[7][7], b[7][7][7][7];typedef struct...{
int bx, by; // 箱子 int px, py; // 人 int step, lev; // 步数} Box;Box q[2500], c, m, g;int inline _check ( int i, int j )...{ return i >= 0 && i < N && j >= 0 && j < M && a[i][j] == 0;}int init ()...{ scanf ( "%d%d", &M, &N ); int i, j; for ( i = 0; i < N; i ++ ) for ( j = 0; j < M; j ++ ) ...{ scanf ( "%d", &a[i][j] ); if ( a[i][j] == 2 ) c.bx = i, c.by = j, a[i][j] = 0; if ( a[i][j] == 3 ) g.bx = i, g.by = j, a[i][j] = 0; if ( a[i][j] == 4 ) m.px = i, m.py = j, a[i][j] = 0;
} memset ( b, 0xff, sizeof ( b ) ); return N;}void bfs ()...{ int pi, pj, pii, pjj, bi, bj, bii, bjj, k, step, lev; int op, ed, ans = 9999; q[0].bx = c.bx, q[0].by = c.by, q[0].px = m.px, q[0].py = m.py; q[0].step = 0, q[0].lev = 0; b[q[0].px][q[0].py][q[0].bx][q[0].by] = 0; int ac; //printf ( "%d %d %d %d ", c.bx, c.by, m.px, m.py ); for ( op = -1, ed = 0; op ++ < ed; ) ...{ Box def = q[op]; pi = def.px, pj = def.py, bi = def.bx, bj = def.by, step = def.step, lev = def.lev; //pb ( pi, pj, bi, bj, step, lev ); if ( bi == g.bx && bj == g.by && def.step < ans ) ...{ //printf ( "%d %d %d %d ", pi, pj, bi, bj ); ans = def.step; } for ( k = 0; k < 4; k ++ ) ...{ pii = pi + dir[k][0], pjj = pj + dir[k][1]; bii = bi, bjj = bj; if ( _check ( pii, pjj ) ) ...{ if ( pii != bi || pjj != bj ) // 人走到空位 ...{ if ( b[pii][pjj][bii][bjj] > step || b[pii][pjj][bii][bjj] == -1 ) ...{ q[++ ed].bx = bii, q[ed].by = bjj, q[ed].px = pii, q[ed].py = pjj; q[ed].step = step, q[ed].lev = lev + 1; b[pii][pjj][bii][bjj] = step; //printf ( "%d %d %d %d ", pii, pjj, bii, bjj ); } } else // 人推箱子 ...{ bii = bi + dir[k][0], bjj = bj + dir[k][1]; if ( _check ( bii, bjj ) ) ...{ if ( b[pii][pjj][bii][bjj] > step + 1 || b[pii][pjj][bii][bjj] == -1 ) ...{ q[++ ed].bx = bii, q[ed].by = bjj, q[ed].px = pii, q[ed].py = pjj; q[ed].step = step + 1, q[ed].lev = lev + 1; b[pii][pjj][bii][bjj] = step + 1; //printf ( "%d %d %d %d ", pii, pjj, bii, bjj ); } } } } } } printf ( "%d ", ans == 9999 ? -1 : ans );}int main ()...{ //freopen ( "in.txt", "r", stdin ); //freopen ( "q1675.in", "r", stdin ); //freopen ( "out.txt", "w", stdout ); while ( init () ) ...{ bfs (); } return 0;}