思路：
一次宽搜就可以解决了。
每个搜索节点需要保存一个 stat 值：如果携带了
shrubbery 则 stat = 1。否则为 0。
地图上的每个点也保存一个 stat 值：如果没经过则stat = 0；如果空着手经过则stat = 1；如果带着
shrubbery经过则stat = 2。判重的时候，如果地图的 stat 值大于搜索节点的 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;
}