http://poj.org/problem?id=1101
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 80;
char cmap[MAXN][MAXN];
bool used[MAXN][MAXN];
short turn[MAXN][MAXN]; // [i,j]'s turn direction
int vis[MAXN][MAXN]; // the number
int w, h, res;
bool isSucceed;
struct node
{
int x, y;
int cnt;
};
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // the direction
bool isOk(int x, int y) // boundary
{
if (x < 0 || x > h || y < 0 || y > w)
return false;
return true;
}
void bfs(node beg, node end) // bfs
{
int i, j;
queue <node> q;
node p, t;
for (i = 0; i <= h; ++i) // init
{
for (j = 0; j <= w; ++j)
{
vis[i][j] = INT_MAX;
used[i][j] = false;
}
} // for
used[beg.x][beg.y] = true;
turn[beg.x][beg.y] = -1;
vis[beg.x][beg.y] = 0;
for (i = 0; i < 4; ++i)
{
p.x = beg.x + dir[i][0];
p.y = beg.y + dir[i][1];
p.cnt = 1;
vis[p.x][p.y] = p.cnt;
used[p.x][p.y] = true;
turn[p.x][p.y] = i;
q.push(p);
}
while (!q.empty())
{
p = q.front();
q.pop();
if (end.x == p.x && end.y == p.y)
{
res = vis[p.x][p.y];
isSucceed = true;
return;
}
if (cmap[p.x][p.y] == 'X')
continue;
for (i = 0; i < 4; ++i)
{
t.x = p.x + dir[i][0];
t.y = p.y + dir[i][1];
if (isOk(t.x, t.y) && !used[t.x][t.y])
{
if (turn[p.x][p.y] == i) // same direction
t.cnt = vis[p.x][p.y];
else t.cnt = vis[p.x][p.y] + 1; // different direction
if (t.cnt < vis[t.x][t.y])
{
vis[t.x][t.y] = t.cnt;
used[t.x][t.y] = true;
turn[t.x][t.y] = i;
q.push(t);
}
}
} // for
} // while
return;
}
int main()
{
char ch;
int i, j, iCount = 0, t;
node beg, end;
while (scanf("%d%d", &w, &h) != EOF && (w + h))
{
w++; h++;
memset(cmap, ' ', sizeof(cmap));
for (i = 1; i < h; ++i)
{
getchar();
for (j = 1; j < w; ++j)
{
scanf("%c", &cmap[i][j]);
}
}
printf("Board #%d:n", ++iCount);
t = 0;
while (scanf("%d%d%d%d", &beg.y, &beg.x, &end.y, &end.x) != EOF) // beg and end
{
if (beg.x == 0 && beg.y == 0 && end.x == 0 && end.y == 0)
break;
res = 0;
isSucceed = false;
bfs(beg, end);
if (isSucceed)
printf("Pair %d: %d segments.n", ++t, res);
else printf("Pair %d: impossible.n", ++t);
}
printf("n");
}
return 0;
}