题意：根据罗马数字与阿拉伯数的对应，在给定表格中，从左边走到右边（不能向左退），相邻格的走，到达右边后，求走过的罗马数字中的
合法串中的最小值。
解法：先通过预处理，建立Trie字典树，利用字典树判断路径串的合法性及其值大小。Trie数据结构+DFS算法。
注意：在DFS过程中，加入合法性判断进行剪枝，可提高效率。若得到整个串时才在Trie树中判断，则会超时。
源代码
#include<iostream>
#include<map>
#include<string>
using namespace std;
const int NLAT = 13;
const int MAXN = 17;
const int INF = 4000;
string lat[NLAT]=
{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
int num[NLAT]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
map<char,int> ch2Int;
char data[MAXN][MAXN];
//字典树节点结构
struct Node
{
int num;
Node *next[7];
};
Node *root; //字典树根节点
int n,m;
int dir[3][2] = {{-1,0},{0,1},{1,0}};
bool visited[MAXN][MAXN];
int minNum;
char ans[101]; //保存当前最优结果
//向字典树中添加新合法串
void Insert(string str, int num)
{
Node *p = root;
string::size_type i = 0;
string::size_type len = str.length();
for(string::size_type i = 0; i<len; i++)
{
int index = ch2Int[str[i]];
if(p->next[index] == NULL)
{
p->next[index] = new Node();
}
p = p->next[index];
}
p->num = num;
}
//构建Trie字典树
void BuildTrieTree()
{
ch2Int['I']=0;
ch2Int['V']=1;
ch2Int['X']=2;
ch2Int['L']=3;
ch2Int['C']=4;
ch2Int['D']=5;
ch2Int['M']=6;
root = new Node();
for(int i=1; i<INF; i++) //1-3999对应的罗马数字串
{
int t = i;
string str = "";
while(t)
{
int j; //此处可稍为优化，每次只从上一次点开始搜索
for(j=0; j<NLAT; j++)
{
if(t >= num[j])
{
break;
}
}
str = str.append(lat[j]);
t -= num[j];
}
Insert(str,i);
}
}
//DFS算法搜索罗马数字串
void DFS(char *res,int x,int y,int ind, Node *ptr)
{
if(y == m-1)
{
if(ptr->num < minNum)
{
minNum = ptr->num;
for(int i=0; i<ind; i++)
{
ans[i] = res[i];
}
ans[ind] = '\0';
}
return;
}
for(int i=0; i<3; i++)
{
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if(dx>=0 && dx<n && dy<m && !visited[dx][dy] && ptr->next[ch2Int[data[dx][dy]]]!=NULL) //判断罗马串是否合法
{
visited[dx][dy] = true;
res[ind++] = data[dx][dy];
DFS(res,dx,dy,ind,ptr->next[ch2Int[data[dx][dy]]]);
visited[dx][dy] = false;
ind--;
}
}
}
//解函数
string Slove()
{
minNum = INF;
char res[101];
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
visited[i][j] = false;
}
}
for(int i=0; i<n; i++) //每行第一个顶点分别为出发顶点
{
visited[i][0] = true;
res[0] = data[i][0];
Node *p = root;
p = p->next[ch2Int[res[0]]];
DFS(res,i,0,1,p);
visited[i][0] = false;
}
if(minNum == INF)
{
return "NO";
}
else
{
return ans;
}
}
int main()
{
BuildTrieTree();
while(cin>>n>>m)
{
for(int i=0; i<n; i++)
{
cin>>data[i];
}
cout<<Slove()<<endl;
}
return 0;
}