题目地址:http://xcacm.hfut.edu.cn/problem.php?id=1007

题目描述

在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。

思路

和昨天那道色子题目差不多,只是难度比昨天稍大,在思维层面。。BFS不解释。

AC代码

/*************************************************************************
    > File Name: 1007.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Thu 28 May 2015 08:37:42 PM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int board[25]; // 初始状态,一维数组,board[1][1] -> board[3][3]用来存放数据
int destboard[25]={0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 0, 8, 0, 4, 0, 0, 7, 6, 5, 0, 0, 0, 0, 0, 0}; // 目标状态
int dx[] = {-1, 0, 1, 0}; // 数字0的移动偏移量
int dy[] = {0, 1, 0, -1};
map<int, bool> mark; // 记录已搜索的状态

int loc(int i, int j) { // 返回i, j二维数组的一维位置
    return i*5 + j;
}

struct Stat{
    int step; // 步数
    int board[25]; // 状态
    Stat(int *b, int s=0) {
        memcpy(this->board, b, sizeof(int)*25);
        step = s;
    }
};

bool ok(int *b) { // 判断是否到达目标状态
    for(int i=1; i<=3; ++i)
        for(int j=1; j<=3; ++j) {
            if(b[loc(i, j)] != destboard[loc(i, j)])
                return false;
        }
    return true;
}

int BFS() {
    queue<Stat> que;
    que.push(Stat(board, 0)); // 初始状态入队
    while(que.size()) {
        int m=0, mk=1; // 记录状态m,以及基数mk
        Stat p = que.front();
        que.pop();

        if(ok(p.board)) { // 到达目标则返回最短步数
            return p.step;
        }
        for(int i=1; i<=3; ++i) // 这个是为了标记初始状态,不能遗漏
            for(int j=1; j<=3; ++j) {
                m+=p.board[loc(i, j)]*mk;
                mk*=10;
            }
        if(!mark.count(m)) // 未标记则标记
            mark[m] = true;

        for(int k=0; k<4; ++k) { // 四个方向搜索
            Stat n(p.board, p.step+1); // n是下一步搜索的状态
            int zx, zy; // zx,zy存放当前状态0的位置

            for(int i=1; i<=3; ++i) // 搜索当前状态的0的位置
                for(int j=1; j<=3; ++j) {
                    if(p.board[loc(i,j)]==0) {
                        zx = i;
                        zy = j;
                        break;
                    }
                    if(p.board[loc(i,j)]==0)
                        break;
                }
            int nx = zx+dx[k]; // 下一个状态的0的位置
            int ny = zy+dy[k];
            m = 0; // 标记状态
            mk = 1;
            swap(n.board[loc(nx, ny)], n.board[loc(zx, zy)]);
            for(int i=1; i<=3; ++i)
                for(int j=1; j<=3; ++j) {
                    m+=n.board[loc(i, j)]*mk;
                    mk*=10;
                }
            if(!mark.count(m)) { // 若未搜索过,则入队
                mark[m] = true;
                que.push(n);
            }
        }
    }
    return -1;
}


int main()
{
#ifdef Oj
     freopen("1007.data/14.in", "r", stdin);
     freopen("1007.data/14.out", "w", stdout);
#endif
    memset(board, 0, sizeof(board));
    for(int i=1; i<=3; ++i)
        for(int j=1; j<=3; ++j)
            scanf("%1d", &board[loc(i, j)]);

    mark.clear();
    cout << BFS() << endl;
    return 0;
}