放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

POJ 2046 Gap 题解《挑战程序设计竞赛》

目录

15-puzzle.svg.png挑战程序设计竞赛第二版.jpg

POJ 2046 Gap 

滑动拼图:也许你玩过15拼图:

15-puzzle.svg.png

可你玩过28拼图吗?给定4*8的表格

gap1.gif

首先把11、21、31、41这四个数字提到第一列空白处:

gap2.gif

然后按如下规则移动数字,定义某个空白处的左邻居+1为魔法数字,如果魔法数字存在,则可以将该魔法数字移动到该空白,比如42旁边的空白可以填充的魔法数字为43,而27则没有魔法数字,因为根本不存在28这个数。

拼图的目标是达到如下效果:

gap3.gif

求最小移动回数

4.5开动脑筋智慧搜索 

剪枝 

题目本身没什么难度,模拟一个游戏规则,用BFS遍历所有状态。

复杂之处在于状态数非常之多,32个格子,28种数字,状态数一共有

hankcs.com 2017-01-21 下午10.35.42.png

不可能用visited[]数组在内存里都表达出来,可以用HashSet来记录visited状态。由于C++98里面没有好用的HashSet,而陈腐的POJ又不支持C++11,所以干脆提交到了AOJ上去了

#include <iostream>
#include <cstring>
#include <climits>
#include <queue>
#include <unordered_set>

using namespace std;

class State
{
public:
    /**
     * 表格数字
     */
    int table[4][8];
    /**
     * 移动回数
     */
    int turn;


    State(int card[4][7])
    {
        for (int i = 0; i < 4; i++)
            table[i][0] = (10 * (i + 1) + 1);// 11 21 31 41
        for (int i = 0; i < 4; i++)
        {
            memcpy(table[i] + 1, card[i], 7 * sizeof(int));
        }
        // 从这种布局开始游戏
        for (int i = 0; i < 4; i++)
        {
            for (int j = 1; j < 8; j++)
            {
                if (table[i][j] == 11 || table[i][j] == 21 || table[i][j] == 31 || table[i][j] == 41)
                    table[i][j] = 0;
            }
        }
        turn = 0;
    }

    State(const State &t)
    {
        memcpy(table, t.table, sizeof(table));
        turn = t.turn;
    }

    /**
     * 可以填充空白
     * @param x
     * @param y
     * @return
     */
    bool can_fill_gap(int x, int y)
    {
        if (table[x][y] != 0)
            return false;
        else if (table[x][y - 1] == 0 || (table[x][y - 1]) % 10 == 7) // x7 has no successor
            return false;
        else
            return true;
    }

    /**
     * 填充空白
     * @param x
     * @param y
     */
    void fill_gap(int x, int y)
    {
        int s, sx, sy;
        sx = sy = -1;

        s = table[x][y - 1] + 1;

        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                if (table[i][j] == s)
                {
                    sx = i;
                    sy = j;
                }
            }
        }

        table[x][y] = table[sx][sy];
        table[sx][sy] = 0;

        turn++;
    }

    /**
     * 是否是游戏结束状态,即每行都是升序,最后一列全为0
     * @return
     */
    bool done()
    {
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 7; j++)
            {
                if (table[i][j] != (10 * (i + 1) + (j + 1)))
                    return false;
            }
            if (table[i][7] != 0)
                return false;
        }

        return true;
    }

    bool operator==(const State &s) const
    {
        int i, j;
        for (i = 0; i < 4; i++)
        {
            for (j = 1; j < 8; j++)
            {
                if (table[i][j] != s.table[i][j])
                    return false;
            }
        }
        return true;
    }

};

struct StateHash
{
    size_t operator()(const State &s) const
    {
        size_t hash = 0;
        for (int i = 0; i < 4; i++)
        {
            for (int j = 1; j < 8; j++)
            {
                hash += s.table[i][j];
                hash <<= 1;
            }
        }

        return hash;
    }
};

int solve(int card[4][7])
{
    queue<State> que;
    unordered_set<State, StateHash> visited;
    //准备BFS
    bool end = false;
    int ans = INT_MAX;
    State init(card);
    if (init.done())
        return 0;
    que.push(init);
    visited.insert(init);
    //BFS
    while (!que.empty() && !end)
    {
        State s = que.front();
        que.pop();
        for (int i = 0; i < 4; i++)
        {
            for (int j = 1; j < 8; j++)
            {
                if (s.can_fill_gap(i, j))
                {
                    State temp(s);
                    temp.fill_gap(i, j);
                    // 结束
                    if (temp.done())
                    {
                        end = true;
                        ans = temp.turn;
                    }// 未遍历
                    else if (visited.find(temp) == visited.end())
                    {
                        que.push(temp);
                        visited.insert(temp);
                    }
                }
            }
        }
    }

    if (ans == INT_MAX)
        ans = -1;
    return ans;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int card[4][7];
        for (int i = 0; i < 4; ++i)
        {
            for (int j = 0; j < 7; ++j)
            {
                scanf("%d", &card[i][j]);
            }
        }

        printf("%d\n", solve(card));
    }
    return 0;
}

hankcs.com 2017-01-21 下午10.16.23.png

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2046 Gap 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机