连连看游戏中的最短路径

连连看游戏是一个比较简单的游戏，两个相同的点可以消除，但前提是两点之间的路径不能有多于两个折点。如何去求解两个点之间的距离呢？我们可以将这里的距离定义为二元组（x，y），x表示多少次转折，y表示路径长度。x值越小距离越短，相同x值的情况下y值越小距离越短。只要使用BFS就可以了，下面就容易写代码了。

#include <iostream>
#include <queue>
using namespace std;

const int N = 20;

int inline getx(int x)
{
    return x & 0xFF;
}

int inline gety(int x)
{
    return (x >> 8) & 0xFF;
}

int inline make(int x, int y)
{
    return (x & 0xFF) | ((y & 0xFF) << 8);
}

bool inline isvalid(int x, int y)
{
    return x >= 0 && y >= 0 && x < N && y < N;
}

char int2char(int i)
{
    return i < 0 ? ' ' : (i < 10 ? '0' + i : (i < 36 ? 'a' + i - 10 :
        (i < 62 ? 'A' + i - 36 : '-')));
}

void print(int map[N][N])
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << int2char(getx(map[i][j])-1) << int2char(gety(map[i][j]));
            if (j != N - 1)
		cout << '.';
        }
        cout << endl;
    }
}

int main()
{
    static int map[N][N];
    static int flg[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = 0;
            flg[i][j] = 0;
        }
    }

    map[0][2] = -1;
    map[1][2] = -1;
    map[2][3] = -1;
    map[2][4] = -1;
    map[3][4] = -1;

    print(map);

    cout << "---

" << endl;
    
    queue<int> q;
    flg[0][0] = 1;
    q.push(make(0, 0));
    while (!q.empty()) {
        int t = q.front();
        int x = getx(t);
        int y = gety(t);
        int u = 1, d = 1, l = 1, r = 1;
        for (int step = 1; step < N; step++) {
            int dist = make(getx(map[x][y])+1, gety(map[x][y])+step);
            if (u && isvalid(x,y-step) && flg[x][y-step] == 0) {
                if (map[x][y-step] != -1) {
                    map[x][y-step] = dist;
                    flg[x][y-step] = 1;
                    q.push(make(x,y-step));
                } else {
                    u = 0;
                }
            }
            if (d && isvalid(x,y+step) && flg[x][y+step] == 0) {
                if (map[x][y+step] != -1) {
                    map[x][y+step] = dist;
                    flg[x][y+step] = 1;
                    q.push(make(x,y+step));
                } else {
                    d = 0;
                }
            }
            if (l && isvalid(x-step,y) && flg[x-step][y] == 0) {
                if (map[x-step][y] != -1) {
                    map[x-step][y] = dist;
                    flg[x-step][y] = 1;
                    q.push(make(x-step,y));
                } else {
                    l = 0;
                }
            }
            if (r && isvalid(x+step,y) && flg[x+step][y] == 0) {
                if (map[x+step][y] != -1) {
                    map[x+step][y] = dist;
                    flg[x+step][y] = 1;
                    q.push(make(x+step,y));
                } else {
                    r = 0;
                }
            }
        }
        q.pop();
    }

    print(map);

    cout << "finish..." << endl;

    return 0;
}