|
|
這題用普通的寬搜可以解決。 關(guān)鍵問題在于由于是寬搜，隊(duì)列里面的元素的step字段必須是從前往后遞增的。 在碰到一大堆聯(lián)通的'X'之后，必須另外進(jìn)行一次遍歷，同時(shí)的把這些'X'插入到隊(duì)列中，保持step字段的遞增。 這樣做復(fù)雜度并不改變。
 #include <stdio.h>
#define NR 1024
  struct node  {
 short x, y;
int s;
 };
char map[NR][NR];
struct node Q[NR*NR];
int W, H;
int sx, sy, ex, ey;
int h, t, h2;
inline int inrange(short x, short y)
{
return x >= 0 && x < W && y >= 0 && y < H;
}
inline void push2(short x, short y, int s)
{
if (!inrange(x, y))
return ;
  if (map[y][x] == 'X' || map[y][x] == '.') {
// printf("p2 %d %d %d\n", x, y, s);
Q[t].x = x;
Q[t].y = y;
if (map[y][x] == '.') {
map[y][x] = '#';
Q[t].s = s + 1;
} else {
map[y][x] = '$';
Q[t].s = s;
 }
t++;
}
}
inline void bfs2(short x, short y, int s)
{
struct node n;
push2(x, y, s);
h2 = t - 1;
while (h2 != t) {
n = Q[h2++];
if (map[n.y][n.x] == '#')
continue;
push2(n.x - 1, n.y, n.s);
push2(n.x + 1, n.y, n.s);
push2(n.x, n.y - 1, n.s);
push2(n.x, n.y + 1, n.s);
}
}
inline void push(short x, short y, int s)
{
if (!inrange(x, y))
return ;
if (map[y][x] == '.') {
// printf("p %d %d %d\n", x, y, s);
Q[t].x = x;
Q[t].y = y;
Q[t].s = s + 1;
t++;
map[y][x] = '@';
} else if (map[y][x] == 'X')
bfs2(x, y, s);
}
inline int bfs()
{
struct node n;
t = h = 0;
push(sx, sy, 0);
while (t != h) {
n = Q[h++];
if (n.x == ex && n.y == ey)
return n.s;
if (map[n.y][n.x] == '$')
continue;
push(n.x - 1, n.y, n.s);
push(n.x + 1, n.y, n.s);
push(n.x, n.y - 1, n.s);
push(n.x, n.y + 1, n.s);
}
}
int main()
{
int i;
while (scanf("%d%d", &H, &W), H) {
for (i = 0; i < H; i++)
scanf("%s", map[i]);
scanf("%d%d%d%d", &sy, &sx, &ey, &ex);
sy--; sx--; ey--; ex--;
printf("%d\n", bfs());
}
return 0;
}
|