Eight II

解题思路

1. 使用IDA*算法进行搜索，同时遍历所有高度中最小的，再保存dfs中的路径就可以了

代码实现

#include <sstream>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<queue>
#include <set>
using namespace std;
const int N = 100;

int T = 1;
int xb[10];//保存数字状态所在的下标方便计算预估函数
int path[N];//保存路径
string now, endd;//起始状态和终止状态
//对应的操作下标
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, -1, 1, 0 };
char op[4] = { 'd', 'l', 'r', 'u' };//因为要字典序最小所以按照字典序遍历

//估值函数，当前状态和目标状态每个点的曼哈顿距离差的和
int f()
{
        int res = 0;

        for (int i = 0; i < 9; i++)
        {
                if (now[i] != 'X')
                {
                        int t = now[i] - '0';
                        res += abs(i / 3 - xb[t] / 3) + abs(i % 3 - xb[t] % 3);
                }
        }
        return res;
}


//因为 dfs 是一条路一条路的搜，并且有回溯。
//所以我们只需要一个 path 即可，后面的会覆盖前面的。
//同样 now 状态只需要一个，回溯会返回状态。

int depth;
bool dfs(int u)
{
        //如果当前深度 + 估值深度 > 最大深度 直接回溯
        if (f() + u > depth) return false;
        if (now == endd) return true; //找到答案了 直接return true

        int X;//找到 X 的位置
        for (int i = 0; i < 9; i++)
        {
                if (now[i] == 'X')
                {
                        X = i;
                        break;
                }
        }
        int x = X / 3, y = X % 3;//一维坐标转换成二维坐标

        for (int i = 0; i < 4; i++)
        {
                int zx = x + dx[i], zy = y + dy[i];

                //优化
                //避免无效操作： 上一个为 l 当前为 r，等于没变化
                if (u != 0 && i + path[u - 1] == 3) continue;
                if (zx < 0 || zx >= 3 || zy < 0 || zy >= 3) continue;

                //change
                swap(now[x * 3 + y], now[zx * 3 + zy]);
                path[u] = i;

                if (dfs(u + 1)) return true;
                //回复现场
                swap(now[x * 3 + y], now[zx * 3 + zy]);
        }

        return false;//如果没有一种分支可以得到终点状态就返回false
}

void solved()
{
        cin >> now >> endd;

        //找到目标状态对应的下标
        for (int i = 0; i < 9; i++) xb[endd[i] - '0'] = i;

        for (depth = 0;; depth++) if (dfs(0)) break;//找到第一个符合条件的深度即最短路径

        cout << "Case " << T++ << ": " << depth << endl;
        for (int i = 0; i < depth; i++) cout << op[path[i]];
        cout << endl;

}


int main()
{
        int t;
        cin >> t;
        while (t--)
        {
                solved();
        }
        return 0;
}

哈密顿绕行世界问题

解题方法

1. dfs直接遍历图再最后判断能不能回到起点可以了

代码实现

#define  _CRT_SECURE_NO_WARNINGS
#include <sstream>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<queue>
#include <set>
#define sc scanf
#define pr printf

using namespace std;

const int N = 21;

//存放走的路径
int path[21];
//链式前向星存图
int cnt = 1;
int head[N];
int to[N * N];
int nxt[N * N];
//一个节点的邻接点
int a[3];
//起点
int m;
//标记数组
int v[N];
//第几条路径
int j = 1;

void dfs(int s, int pos) {
        if (pos == 21 && path[pos - 1] == m) {//如果遍历完了图并且也可以回到起点，那么就打印路径
                pr("%d:  ", j++);
                for (int i = 0; i < pos; i++) {
                        pr("%d ", path[i]);
                }
                pr("\n");
        }

    //遍历节点的边
        for (int i = head[s]; i; i = nxt[i]) {
                if (!v[to[i]]) {
                        path[pos] = to[i];
                        v[to[i]] = 1;
                        dfs(to[i], pos + 1);
                        v[to[i]] = 0;
                }       
        }
}

bool compare(int a, int b)
{
        // 升序排列，如果改为return a>b ,则为降序
        return a > b;
}

void add(int from, int t)
{
        nxt[cnt] = head[from];
        to[cnt] = t;
        head[from] = cnt++;
}

int main() {
        for (int i = 1; i <= 20; i++) {
                sc("%d%d%d", a, a + 1, a + 2);

                sort(a, a + 3, compare);//保证数组是升序的，那么就可以保证输出的时候是字典序最小

                add(i, a[0]);
                add(i, a[1]);
                add(i, a[2]);
        }

        while (sc("%d", &m), m) {
                path[0] = m;
                dfs(m, 1);
                memset(v, 0, sizeof(v));
                j = 1;
        }

        return 0;
}