思路：
一次寬搜就可以解決了。
每個搜索節(jié)點需要保存一個 stat 值：如果攜帶了
shrubbery 則 stat = 1。否則為 0。
地圖上的每個點也保存一個 stat 值：如果沒經(jīng)過則stat = 0；如果空著手經(jīng)過則stat = 1；如果帶著
shrubbery經(jīng)過則stat = 2。判重的時候，如果地圖的 stat 值大于搜索節(jié)點的 stat 值就可以忽略了。
代碼 266ms：
#include <stdio.h>
#define SIZE 1024
struct map_node 
{
int type, stat;
};
struct map_node map[SIZE][SIZE];
struct queue_node {
int step, x, y, stat;
};
struct queue_node queue[SIZE * SIZE * 2];
int W, H, qh, qt;
__inline int push(int y, int x, int stat, int step)
{
if (y < 0 || y >= H || x < 0 || x >= W)
return 0;
if (map[y][x].type == 1)
return 0;
if (map[y][x].type == 3)
return stat;
if (map[y][x].type == 4)
stat = 1;
if (map[y][x].stat > stat)
return 0;
map[y][x].stat++;
queue[qt].stat = stat;
queue[qt].y = y;
queue[qt].x = x;
queue[qt].step = step;
qt++;
return 0;
}
int main()
{
int i, j;
struct queue_node *t;
freopen("e:\\test\\in.txt", "r", stdin);
t = &queue[qt++];
scanf("%d%d", &W, &H);
for (i = 0; i < H; i++) {
for (j = 0; j < W; j++) {
scanf("%d", &map[i][j].type);
if (map[i][j].type == 2) {
t->y = i;
t->x = j;
}
}
}
while (qh != qt) {
t = &queue[qh++];
if (push(t->y - 1, t->x, t->stat, t->step + 1) ||
push(t->y + 1, t->x, t->stat, t->step + 1) ||
push(t->y, t->x - 1, t->stat, t->step + 1) ||
push(t->y, t->x + 1, t->stat, t->step + 1)
)
break;
}
printf("%d\n", t->step + 1);
return 0;
}