放牧代码和思想
专注自然语言处理、机器学习算法

AOJ 2212 Stolen Jewel 题解《挑战程序设计竞赛》

目录

stolenjewel1.png挑战程序设计竞赛第二版.jpg

AOJ 2212 Stolen Jewel 

夺宝奇兵:某国国宝失窃,你千辛万苦追回珍宝,正准备上交给国家时,却被怀疑是赝品。为了鉴别真伪,需要将宝石放到迷宫的魔法阵中。但迷宫中有特殊机关,不允许特定的移动模式。如下图的移动方式是错误的

stolenjewel1.png

而下图才是正确的打开方式

stolenjewel2.png

给定地图和禁止模式,求抵达魔法阵所需最少步数。

输入数据第一行是地图的行数N和列数M。

接着是H行W列字符地图,字符意义如下:

S 入口

G 魔法阵

. 通道

# 墙壁

接着一个整数P代表禁止移动模式的个数,然后是P行模式串,其组成字符意义如下:

UDLR分别代表上下左右。

输出一个整数,代表最低步数。如果无法抵达魔法阵,则输出-1。

4.7华丽地处理字符串 

动态规划算法 

谈起字符串算法,应该算是我的老本行了。

主框架是BFS,在普通的BFS中,搜索状态用二维数组bool visited[x][y]记录。在这里当前搜索状态一共有两个要素,一是当前坐标,二是当前字符串。用模式串构造trie树,则当前字符串等效为trie树的某个节点。于是可以按如下方式记录访问状态:

set<Node *> visited[50][50];

在遍历的过程中,如何判断当前路径中是否含有非法模式串呢?多模式匹配就上AC自动机了。也可以用后缀trie树,但本质上AC自动机就是前缀trie树与后缀trie树的结合体。由于AC自动机的模板更好找,就懒得写后缀树了。

#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <string>
#include <set>

using namespace std;
#define INF 0x3f3f3f3f

// Aho Corasick
struct Node
{
    map<char, Node *> next;
    Node *fail;
    vector<int> match;

    Node() : fail(NULL)
    {}
};

Node *build(vector<string> pattens)
{
    // 1. 构建trie树
    Node *root = new Node();
    root->fail = root;
    for (int i = 0; i < pattens.size(); i++)
    {
        Node *p = root;
        for (auto c : pattens[i])
        {
            if (p->next[c] == 0)
                p->next[c] = new Node();
            p = p->next[c];
        }
        p->match.push_back(i);
    }

    // 2. failure表
    queue<Node *> que;
    for (int i = 0; i < 128; i++)
    {
        if (!root->next[i])
        {
            root->next[i] = root;
        }
        else
        {
            root->next[i]->fail = root;
            que.push(root->next[i]);
        }

    }
    while (!que.empty())
    {
        Node *p = que.front();
        que.pop();
        for (auto a : p->next)
        {
            int i = a.first;
            Node *np = a.second;
            if (!np)
                continue;

            // add que
            que.push(np);

            // search failure link
            Node *f = p->fail;
            while (!f->next[i])
                f = f->fail;
            np->fail = f->next[i];

            // update matching list
            np->match.insert(np->match.end(), np->fail->match.begin(), np->fail->match.end());
        }
    }
    return root;
}

// Trie树节点 p 接受字符 c 转移
Node *next_node(Node *p, char c)
{
    while (!p->next[c])
        p = p->fail;
    return p->next[c];
}

Node *next_node(Node *p, string query)
{
    for (char c : query)
    {
        p = next_node(p, c);
    }
    return p;
}

class State
{
public:
    int x;
    int y;
    int cost;
    string path;

    State(int x, int y, int cost, const string &path) : x(x), y(y), cost(cost), path(path)
    {}

    bool operator<(const State &s) const
    {
        return cost < s.cost;
    }

    bool operator>(const State &s) const
    {
        return cost > s.cost;
    }
};

int tx[] = {0, 1, 0, -1};       //URDL
int ty[] = {-1, 0, 1, 0};
const static string dir_str[4] = {"U", "R", "D", "L"};

int main()
{
    int H, W;
    while (~scanf("%d %d", &H, &W), H)
    {
        char stage[50][50];
        set<Node *> visited[50][50];

        int sx = 0;
        int sy = 0;
        int gx = 0;
        int gy = 0;
        for (int y = 0; y < H; y++)
        {
            char line[51];
            scanf("%s", line);
            for (int x = 0; x < W; x++)
            {
                stage[y][x] = line[x];
                if (line[x] == 'S')
                {
                    sx = x;
                    sy = y;
                }
                else if (line[x] == 'G')
                {
                    gx = x;
                    gy = y;
                }
            }
        }
        int total_prohibited_sequences;
        scanf("%d", &total_prohibited_sequences);

        vector<string> keywords(total_prohibited_sequences);
        for (int sequence_idx = 0; sequence_idx < total_prohibited_sequences; sequence_idx++)
        {
            cin >> keywords[sequence_idx];
        }

        Node *root = build(keywords);

        // BFS
        priority_queue<State, vector<State>, greater<State> > que;
        que.push(State(sx, sy, 0, ""));

        int ans = INF;
        while (!que.empty())
        {
            State s = que.top();
            que.pop();
            string route = s.path;
            int cost = s.cost;
            int sx = s.x;
            int sy = s.y;

            for (int i = 0; i < 4; i++)
            {
                int dx = sx + tx[i];
                int dy = sy + ty[i];
                if (dx < 0 || dx >= W || dy < 0 || dy >= H)
                    continue;

                if (stage[dy][dx] == '#')
                    continue;

                string next = route + dir_str[i];
                if (next.size() > 10)   // 剪枝策略,题目限定禁止模式的长度不超过10
                    next = next.substr(next.size() - 10);

                auto p = next_node(root, next);
                if (p->match.size())
                {
                    continue;
                }

                if (visited[dy][dx].count(p)) // 已经访问过这个状态
                    continue;
                visited[dy][dx].insert(p);

                if (stage[dy][dx] == 'G')
                {
                    ans = cost + 1;
                    goto found;
                }

                que.push(State(dx, dy, cost + 1, next));
            }
        }

        found:;
        printf("%d\n", ans == INF ? -1 : ans);
    }
}

hankcs.com 2017-02-03 下午11.00.33.png

恭喜,锦旗一面和500软妹币已发货

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

分享到:更多 ()

评论 欢迎留言

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

我的开源项目

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