POJ 2488 3278

• POJ 2488 3278
  • 简单搜索
    • 深度优先搜索
    • 广度优先遍历

简单搜索

深度优先搜索

2488 18-08-23

这道题如果没有看到深搜的分类，可能思路这么清晰，并且知道是深搜之后也是愣了一下才想到。

主要在于如何将一个走棋的问题转换为一个图，由于走马对于走的方向是由强制性规定的，所以可以将每一个格子看作无向图中的一个顶点，如果两个格子之间符合“日”字走法，则这两个顶点之间有一条边，于是是否能遍历所有格子则变成了是否能够不回头的走完所有点，后来问了ssy才知道是求哈密顿链的问题。哈密顿链、半哈密顿图、哈密顿回路和哈密顿图的定义在离散数学教材上都能找到（注意和欧拉图看似相似但没有联系，欧拉图可以不是哈密顿图，哈密顿图也可以不是欧拉图），但是对于本题来说，这些点并不符合哈密顿链的充分条件，即设G为具有n个顶点的无向图（根据后面的条件可以证明其为连通图），若G中每一对顶点的度数和大于等于n-1，则G中存在哈密顿链。虽然直觉上一定是从角开始走，但一开始为了保险，我从每个点都进行了一次DFS，结果是TLE，于是就改成了只从A1角开始DFS，则成功AC。但是我疑惑的就是，为什么如下命题成立：如果这个棋盘的无向图存在哈密顿链，则必有哈密顿链从角上出发，可惜的是在网上也没有看到太多的解答，待研究。做了一张图，星表示从该点出发可以遍历全图。

除了DFS，另一个需要使用的是回溯。因为在DFS的过程中，我们不期望出现类似“树枝”的结果，这样就不是哈密顿链了，所以当我们在一个分支走入死路并且往回走到分岔点的时候，我们希望将这条分叉上经过的点设为“未经过”，这样就可以让另外一个分支重新探索这些点。

另外根据exp-blog，通过安排探索的顺序，是可以做到不用记录所有合法路径的，第一条合法路径就是字典序的最小路径。不过我猜测这个方法很可能会在数字轴两位数的棋盘（当然字母轴也不能太小）上失效。

#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <iostream>
const int N = 27;
const int move[8][2] = {{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}};
int n, p, q;
std::vector<int> connected_nodes[N];
bool visited[N];
std::vector<int> temp_path; // 当前搜索产生的路径
std::vector<std::string> paths;
std::string id2str(int node_id)
{
    char letter = 'A' + node_id / p;
    char number = '1' + (node_id % p);
    std::string result = "";
    result += letter;
    result += number;
    return result;
}
void dfs(int o)
{
    visited[o] = true;
    temp_path.push_back(o);
    bool node_visited = true;
    for (std::vector<int>::iterator iter = connected_nodes[o].begin(); iter != connected_nodes[o].end(); ++iter)
    {
        if (!visited[*iter])
        {
            node_visited = false;
            dfs(*iter);
        }
    }
    if (node_visited)
    {
        bool all_visited = true;
        for (int i = 0; all_visited && i < p * q; ++i)
        {
            if (!visited[i])
                all_visited = false;
        }
        if (all_visited)
        {
            std::string result = "";
            for (std::vector<int>::iterator iter = temp_path.begin(); iter != temp_path.end(); ++iter)
                result += id2str(*iter);
            paths.push_back(result);
        }
    }
    visited[o] = false;
    temp_path.pop_back();
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    for (int case_id = 1; case_id <= n; ++case_id)
    {
        memset(visited, 0, sizeof(visited));
        std::cin >> p >> q;
        std::cout << "Scenario #" << case_id << ":" << std::endl;
        int origin_id, dest_id, dest_i, dest_j;
        for (int i = 0; i < q; ++i)
        {
            for (int j = 0; j < p; ++j)
            {
                origin_id = i * p + j;
                for (int k = 0; k < 8; ++k)
                {
                    dest_i = i + move[k][0];
                    dest_j = j + move[k][1];
                    if (dest_i >= 0 && dest_i < q && dest_j >= 0 && dest_j < p)
                    {
                        dest_id = dest_i * p + dest_j;
                        connected_nodes[origin_id].push_back(dest_id);
                    }
                }
            }
        }
        /*
        for (int i = 0; i < p * q; ++i)
        {
            std::cout << id2str(i) << ": ";
            for (std::vector<int>::iterator iter = connected_nodes[i].begin(); iter != connected_nodes[i].end(); ++iter)
                std::cout << id2str(*iter) << " ";
            std::cout << std::endl;
        }
        */
        /* 只需要从第一角开始遍历
        for (int i = 0; i < q; ++i)
            for (int j = 0; j < p; ++j)
                dfs(i * p + j);
        */
        dfs(0);
        sort(paths.begin(), paths.end());
        if (paths.size() == 0)
            std::cout << "impossible" << std::endl;
        else
            std::cout << paths[0] << std::endl;
        for (int i = 0; i < p * q; ++i)
            connected_nodes[i].clear();
        paths.clear();
        temp_path.clear();
    }
}

广度优先遍历

3278 2018-08-25

水题一道（当然是知道它是什么类型的情况下hhh），一开始交还TLE了，因为没有考虑每次乘3队列中的数量就会幂级增长，应该通过标志位来标志节点已经被访问。主要内容就是将奶牛的过程转换为BFS的问题，为什么是BFS呢，当然是因为在BFS下第一次找到奶牛的时候一定是深度最小的情况，每进行一次walking或者teleporting，都将该点的深度置为当前点+1并push入队列。

#include <cstdio>
#include <queue>
const int N = 100000;
struct node
{
    int position;
    int depth;
};
std::queue<node> q;
bool visited[N + 5] = { 0 };
int bfs(int origin, int dest)
{
    q.push(node {origin, 0});
    int position, depth;
    while (true)
    {
        node& now = q.front();
        position = now.position;
        depth = now.depth;
        visited[position] = true;
        q.pop();
        if (position == dest)
            return depth;
        if (position * 2 <= N && !visited[position * 2])
            q.push(node {position * 2, depth + 1});
        if (position > 0 && !visited[position - 1])
            q.push(node {position - 1, depth + 1});
        if (position < N && !visited[position + 1])
            q.push(node {position + 1, depth + 1});
    }
}
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    printf("%d\n", bfs(n, k));
}