Poj Solution 1101

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;
}