AOJ 0121 广度优先搜索 - 7hat - 博客园

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121
2.1 最基础的“穷竭搜索” 广度优先搜索
题意：7数码问题。在2×4的棋盘上，摆有7个棋子，每个棋子上标有1至7的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（用0表示），与空格相邻（上下左右）的棋子可以移到空格中，该棋子原先位置成为空格。给出一个初始状态（保证可以转移到最终状态），找出一种从初始状态转变成给定最终状态的移动棋子步数最少的移动步骤。
输入：多组输入，每组8个数，表示初始状态前四个数为第一行从左到右，后四个数为第二行从左到右。 
输出：至少需要多少步可以从输入状态到达最终状态（0 1 2 3 4 5 6 7） 
（题意翻译参考自http://bbs.byr.cn/#!article/ACM_ICPC/73337?au=Milrivel）
（图1）
　　(图2)
　　（图3）
分析：
乍一看这题没从入手，但只要采取逆向思维，还是可以用广度优先搜索解决。先不考虑如何用最小步数从输入状态到达最终状态，所有结果的最终状态都是（01234567），那么反过来想，只要求出最终状态到达所有结果时的最小步数并记录下来，接下来就是查表了。0表示空位置，对空位置周围的格子采用广度优先的方式移动到0，并记录下最小步数的结果即可。如上图所示，图1，可以选择让7移动过来变成图2，也可以选择让2移动过来变成图3。我们要做的只不过是不断重复这种选择，直至穷举所有情况并记录结果。
我主要是用一个map<string, int>来表示(01234567)到string 的最小步数int，只要当前结果还不存在，就加入map，必然能够穷尽状态。另外，在移动格子问题上，因为我采用string来表示当前状态，那么移动方向上下左右分别就是当前位置-4, +4, -1, +1。需要注意的是，位置3不能移动到位置4.
http://www.hankcs.com/program/aoj-0121-seven-puzzle-challenge-programming-contest-2nd-edition-exercises-answers.html

思路：与前几题的bfs不同，这次的bfs没有明确的移动对象，看似任意一个数都可以当成对象移动。这时我们只需要抓住一个格子就行，比如我们把0作为移动对象，那么0在地图中漫游所有的格子得到的肯定就是问题的解空间。由于题目的输入是多个case，如果对每个case都运行一遍bfs就会TLE。这时我们祭出dp技能，只需要一次bfs就将解空间算出来，以后每个case只要到解空间中去找就行了。

map<string, int> dp;

int direction[4] = { 1, -1, 4, -4 };

void bfs()

{

    queue<string> que;

    que.push("01234567");

    dp["01234567"] = 0;

    while (!que.empty())

    {

        string now = que.front(); que.pop();

        // p是'0'的位置

        int p = 0;

        for (int j = 0; j < 8; ++j)

        {

            if (now[j] == '0')

            {

                p = j;

                break;

            }

        }

        for (int i = 0; i < 4; ++i)

        {

            int n = p + direction[i];

            if (0 <= n && n < 8 && 

                !(p == 3 && i == 0) && // 右上角不能再往右了

                !(p == 4 && i == 1))   // 左下角不能再往左了

            {

                string next = now;

                swap(next[p], next[n]);

                if (dp.find(next) == dp.end())

                {

                    dp[next] = dp[now] + 1;

                    que.push(next);

                }

            }

        }

    }

}

int main(int argc, char *argv[])

{

 

    bfs();

    string line;

    while (getline(cin, line))

    {

        line.erase(remove(line.begin(), line.end(), ' '), line.end());

        cout << dp[line] << endl;

    }

 

    return 0;

}

Also check http://www.cnblogs.com/7hat/p/3597754.html
Read full article from AOJ 0121 广度优先搜索 - 7hat - 博客园