放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

UVa 10181 15-Puzzle Problem 题解《挑战程序设计竞赛》

目录

hankcs.com 2017-01-25 下午10.13.30.png挑战程序设计竞赛第二版.jpg

UVa 10181 15-Puzzle Problem 

滑动拼图:给定拼图,求解决方案。hankcs.com 2017-01-25 下午10.13.30.png

hankcs.com 2017-01-25 下午9.32.55.png

4.5开动脑筋智慧搜索 

A*与IDA* 

滑块拼图问题是否有解的判断方法是,先将表格平铺:

hankcs.com 2017-01-25 下午9.32.39.png

然后计算N=逆序数对之和,e=空白所在的行数。若N+e为偶数,则有解,反之无解,证明在此

然后估计最优解的下界,对所有非0数字,最理想的情况是表格中其他数字都不存在,不浪费一步避让,一路畅通无阻抵达目标。此时所需的步数为曼哈顿距离hankcs.com 2017-01-25 下午9.46.23.png

hankcs.com 2017-01-25 下午9.45.33.png

之后就是常规的IDA*搜索了。

#include <iostream>
#include <climits>
#include <string>
#include <algorithm>

using namespace std;

const int dy[4] = {0, 0, +1, -1};
const int dx[4] = {+1, -1, 0, 0};
const int direction[4] = {'R', 'L', 'D', 'U'};
const int MAX_N = 50;
string path;
int T[15][15], e_y, e_x;

// 最优解下界
int h()
{
    int limit = 0;
    for (int y = 0; y < 4; y++)
    {
        for (int x = 0; x < 4; x++)
        {
            if (T[y][x] == 0)
                continue;
            int goal_y = (T[y][x] - 1) / 4;
            int goal_x = (T[y][x] - 1) % 4;
            limit += abs(goal_y - y) + abs(goal_x - x); // 曼哈顿距离
        }
    }
    return limit;
}

bool dfs(int current_steps, int prev_direction, int bound)
{
    int limit = h();
    if (limit == 0)
        return true;
    if (current_steps + limit > bound)
        return false;

    for (int i = 0; i < 4; i++)
    {
        if (i == (prev_direction ^ 1))  // 小三爷,不回头
            continue;

        int ny = e_y + dy[i];
        int nx = e_x + dx[i];
        if (ny < 0 || ny >= 4)
            continue;
        if (nx < 0 || nx >= 4)
            continue;

        path.push_back(direction[i]);
        swap(T[ny][nx], T[e_y][e_x]);
        swap(ny, e_y);
        swap(nx, e_x);
        if (dfs(current_steps + 1, i, bound))
            return true;
        swap(ny, e_y);
        swap(nx, e_x);
        swap(T[ny][nx], T[e_y][e_x]);
        path.pop_back();
    }

    return false;
}

bool ida_star()
{
    for (int limit = h(); limit <= MAX_N; ++limit)
    {
        if (dfs(0, -1, limit))
            return true;
    }
    return false;
}

bool solvable()
{
    int N = 0;
    bool occur[16] = {false};
    for (int y = 0; y < 4; y++)
    {
        for (int x = 0; x < 4; x++)
        {
            if (T[y][x] == 0)
            {
                e_y = y;
                e_x = x;
            }
            else
            {
                N += count(occur + 1, occur + T[y][x], false);
                occur[T[y][x]] = true;
            }
        }
    }
    return ((N + (e_y + 1)) & 1) == 0;  // N + e 为偶数,则当前局面有解,否则无解
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int N;
    scanf("%d", &N);
    while (N--)
    {
        for (int y = 0; y < 4; y++)
        {
            for (int x = 0; x < 4; x++)
            {
                scanf("%d", &T[y][x]);
            }
        }
        path.clear();
        if (!solvable() || !ida_star())
        {
            puts("This puzzle is not solvable.");
        }
        else
        {
            printf("%s\n", path.c_str());
        }
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

hankcs.com 2017-01-25 下午10.10.36.png

Reference

https://amoshyc.github.io/ojsolution-build/uva/p10181.html

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

分享到:更多 ()

评论 欢迎留言

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

我的开源项目

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