码农场
夺宝奇兵：某国国宝失窃，你千辛万苦追回珍宝，正准备上交给国家时，却被怀疑是赝品。为了鉴别真伪，需要将宝石放到迷宫的魔法阵中。但迷宫中有特殊机关，不允许特定的移动模式。如下图的移动方式是错误的
而下图才是正确的打开方式
给定地图和禁止模式，求抵达魔法阵所需最少步数。
输入数据第一行是地图的行数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);
}
}
恭喜，锦旗一面和500软妹币已发货
知识共享署名-非商业性使用-相同方式共享：码农场 » AOJ 2212 Stolen Jewel 题解《挑战程序设计竞赛》