解题思路：DF
源代码：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
//存放字母表
private static Dictionary<char, int> m_WordsDic;
//int是每个word在callnumber中匹配的index位置，每个index对应的point可能是多个
private static Dictionary<int,List<Point>> m_Wordspath;
//将每个word转为digital
private static List<Words> m_Digitals;
private static Mark[] m_MinPath;
static void Main(string[] args)
{
while (true)
{
//初始化
Init();
string callNum;
int n;
//第一行是call number
callNum = Console.ReadLine();
if (callNum == "-1")
break;
//第二行是下面有多少word
n = int.Parse(Console.ReadLine());
//进行word存储
//word转化为数字
InitDigitalDic(n);
//生成wordPathDic
InitPathDic(callNum);
m_MinPath=new Mark[callNum.Length];
for (int i = 0; i < callNum.Length; i++)
{
m_MinPath[i]=new Mark();
}
InitPathMin(callNum.Length);
if (m_MinPath[callNum.Length-1].Num == 0)
{
//没有找到路径
Console.WriteLine("No solution.");
}
else
{
foreach (Point point in m_MinPath[callNum.Length-1].MarkPoints)
{
var markResult = new List<Point> {point};
if (OutPutResult(point, markResult, m_MinPath[callNum.Length - 1].Num))
break;
}
}
}
//Console.ReadLine();
}
private static bool OutPutResult(Point point,List<Point> mark,int count)
{
if (count == 1 && point.StartIndex != 0)
{
//搜寻失败
return false;
}
//是否到达原点
if(point.StartIndex==0)
{
//换行，开始下一个最短解
OutPutMark(mark);
return true;
}
//如果没到达原点，那么继续往上回溯
foreach (Point p in m_MinPath[point.StartIndex-1].MarkPoints)
{
mark.Add(p);
if (OutPutResult(p, mark, (count - 1)))
return true;
mark.Remove(p);
}
return false;
}
private static void OutPutMark(List<Point> mark)
{
StringBuilder sb=new StringBuilder();
for (var i = mark.Count-1; i >=0; i--)
{
sb.Append(string.Format("{0} ", mark[i].Words.Letters));
}
Console.WriteLine(sb.ToString(0, sb.Length - 1));
}
private static void InitPathMin(int n)
{
List<Point> StartList = null;
if (m_Wordspath.TryGetValue(0, out StartList))
{
//初始化第一点
foreach (Point point in StartList)
{
NextPoint(point, n);
}
}
}
private static void AddMark(ref Mark mark,int num,Point point)
{
mark.Num = num;
mark.MarkPoints.Add(point);
}
private static void NextPoint(Point prePoint,int n)
{
List<Point> list = null;
int index = prePoint.EndIndex + 1;
//开始对该点最小值进行对比生成
if(!MinPoint(prePoint))
return;
if (prePoint.EndIndex == n)
{
//如果是终点，直接返回
return;
}
//如果dic这点无值，意味着死路
if(!m_Wordspath.TryGetValue(index,out list))
{
return;
}
//获得以该index作起始点的list
foreach (Point point in list)
{
//开始层的搜寻
NextPoint(point, n);
}
}
private static bool MinPoint(Point point)
{
var mark = m_MinPath[point.EndIndex];
int temp = 1;
//如果是第一点
if (point.StartIndex - 1 >= 0)
temp = m_MinPath[point.StartIndex - 1].Num + 1;
if (mark.Num == 0)
{
//如果未初始化，直接赋值
AddMark(ref mark, temp, point);
return true;
}
if(temp<mark.Num)
{
mark.MarkPoints.Clear();
AddMark(ref mark, temp, point);
return true;
}
if (temp == mark.Num)
{
if (!NotContains(mark, point))
{
AddMark(ref mark, temp, point);
return false;
}
}
return false;
}
private static bool NotContains(Mark mark, Point point)
{
return mark.MarkPoints.Any(r => r.StartIndex == point.StartIndex && r.EndIndex == point.EndIndex&&r.Words.Letters==point.Words.Letters);
}
private static void InitPathDic(string callNum)
{
foreach (Words mDigital in m_Digitals)
{
FindNextIndex(0,callNum, mDigital);
}
}
private static void FindNextIndex(int startIndex,string lest,Words words)
{
//如果未找到，那么就返回
int index = lest.IndexOf(words.Digital);
if (index == -1)
return;
int endIndex = index + words.Digital.Length - 1;
AddPoint(index + startIndex, endIndex + startIndex, words);
FindNextIndex(index + 1 + startIndex, lest.Substring(index + 1), words);
//index += startIndex;
////如果找到了，添加point，用剩下的stirng继续找匹配
//int lastIndex = index + words.Digital.Length;
//AddPoint(index, lastIndex, words);
//FindNextIndex(startIndex + 1, lest.Substring(1), words);
}
private static void AddPoint(int startIndex,int lastIndex,Words words)
{
List<Point> temp = null;
if(m_Wordspath.TryGetValue(startIndex,out temp))
{
//如果已经存在该项，那么不做添加
if (!temp.Any(r => r.StartIndex == startIndex && r.EndIndex == lastIndex && r.Words == words))
temp.Add(new Point(startIndex, lastIndex, words));
}
else
{
m_Wordspath[startIndex] = new List<Point>() { new Point(startIndex, lastIndex, words) };
}
}
private static void InitDigitalDic(int n)
{
for (int i = 0; i < n; i++)
{
string lineValue = Console.ReadLine();
var sb = new StringBuilder();
foreach (char c in lineValue)
{
sb.Append(m_WordsDic[c]);
}
m_Digitals.Add(new Words(sb.ToString(), lineValue));
}
}
private static void Init()
{
m_Digitals = new List<Words>();
m_WordsDic = new Dictionary<char, int>()
{
{'i', 1},
{'j', 1},
{'a', 2},
{'b', 2},
{'c', 2},
{'d', 3},
{'e', 3},
{'f', 3},
{'g', 4},
{'h', 4},
{'k', 5},
{'l', 5},
{'m', 6},
{'n', 6},
{'p', 7},
{'r', 7},
{'s', 7},
{'t', 8},
{'u', 8},
{'v', 8},
{'w', 9},
{'x', 9},
{'y', 9},
{'o', 0},
{'q', 0},
{'z', 0},
};
m_Wordspath = new Dictionary<int, List<Point>>();
}
}
class Point
{
public int StartIndex;
public int EndIndex;
public Words Words;
public Point(int startIndex,int endIndex,Words letters)
{
StartIndex = startIndex;
EndIndex = endIndex;
Words = letters;
}
}
class Words
{
public string Digital;
public string Letters;
public Words(string digital,string letter)
{
Digital = digital;
Letters = letter;
}
}
class Mark
{
public int Num;
public List<Point> MarkPoints;
public Mark()
{
MarkPoints = new List<Point>();
}
}