学步园

Timus 1603. Erudite 要求解一个字谜。

---

1603. Erudite

Time Limit: 1.0 second
Memory Limit: 64 MB

Petr likes to solve crossword puzzles and other conundrums. Once he found in a newspaper
a new puzzle called "Erudite". There was a square table 4 × 4 filled with
letters. It was required to find in the table as many words as possible;
the words could go up, down, to the right, or to the left and
break at right angles any number of times but they could not have self-intersections.

Petr's friend Vasya told him that it was very silly to spend time solving this
puzzle. He told it was much easier to write a program that would search for
the required words in a dictionary. Petr was offended and told Vasya: "If
you are that clever, write the program yourself. I will cope with the puzzle
myself, the way I like." Help Vasya to get out of the situation.
You should write this program.

Input

The first four lines of the input contain a table 4 × 4 consisting of
lowercase English letters. In the next line there is the number n
(n ≤ 100) of words in the dictionary. These words are given in the
following n lines, one word per line. Each word consists of
lowercase English letters and has length from 1 to 16.

Output

For each word from the dictionary output "YES" if this word can be found in
the table and "NO" otherwise. Use the format given in the sample.

Sample

input	output
abra adac babr arca 3 abracadabra ababaab ababaaba	abracadabra: YES ababaab: YES ababaaba: NO

Problem Author: Vladimir Yakovlev
Problem Source: IX USU Open Personal Contest (March 1, 2008)

---

解答如下：

 1 using System;
 2 
 3 namespace Skyiv.Ben.Timus
 4 {
 5   // http://acm.timus.ru/problem.aspx?space=1&num=1603
 6   sealed class T1603a
 7   {
 8     static void Main()
 9     {
10       const int size = 4;
11       const char border = ' '; // 用于设定边界，以便在搜索时不用担心越界
12       string[] table = new string[size + 2];
13       table[0] = table[size + 1] = new String(border, size + 2);
14       for (int i = 1; i <= size; i++) table[i] = border + Console.ReadLine() + border;
15       for (int i = int.Parse(Console.ReadLine()); i > 0; i--)
16       {
17         string word = Console.ReadLine();
18         bool find = false;
19         bool[,] mark = new bool[size + 2, size + 2];
20         for (int x = 1; !find && x <= size; x++)
21           for (int y = 1; !find && y <= size; y++)
22           {
23             if (table[y][x] != word[0]) continue;
24             Array.Clear(mark, 0, mark.Length);
25             find = Search(word, table, mark, y, x, 1); // 深度优先搜索
26           }
27         Console.WriteLine(word + ": " + (find ? "YES" : "NO"));
28       }
29     }
30 
31     static readonly int[,] direction = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
32 
33     static bool Search(string word, string[] table, bool[,] mark, int y, int x, int depth)
34     {
35       if (mark[y, x]) return false;
36       mark[y, x] = true;
37       if (depth == word.Length) return true;
38       for (int i = 0; i < 4; i++)
39       {
40         int y1 = y + direction[i, 0];
41         int x1 = x + direction[i, 1];
42         if (table[y1][x1] == word[depth] && Search(word, table, mark, y1, x1, depth + 1)) return true;
43       }
44       return mark[y, x] = false;
45     }
46   }
47 }

这个题目首先给出一个 4x4 的字谜，然后给出许多单词，要求你判断这些单词是否能够由前面的字谜组成。规则是，你能够在字谜中上下左右行走，也能够拐弯，但是已经使用过的字母不允许再用。

这个程序首先读入这个字谜。为了方便后面在字谜中搜索时不用判断是否会越界，读入字谜时在字谜的四周围了一圈边界。然后就是逐个读入单词，在字谜的每个位置开始使用深度优先搜索遍历字谜，就是在程序中第 25 行的语句通过递归调用第 33 到 45 行的 Search 方法。

这个程序还可以进一步改进，就是在遍历字谜之前先判断一下所给的单词中的字母是否都在字谜中，还有每一个字母出现的次数是否比字谜中相应字母出现的次数更多。要实现这点，需要在读入字谜时记录每个字母出现的次数。修改后的程序如下所示：

 1 using System;
 2 using System.Collections.Generic;
 3 
 4 namespace Skyiv.Ben.Timus
 5 {
 6   // http://acm.timus.ru/problem.aspx?space=1&num=1603
 7   sealed class T1603b
 8   {
 9     static void Main()
10     {
11       const int size = 4;
12       const char border = ' '; // 用于设定边界，以便在搜索时不用担心越界
13       string[] table = new string[size + 2];
14       table[0] = table[size + 1] = new String(border, size + 2);
15       Dictionary<char, int> charCount = new Dictionary<char, int>();
16       for (int i = 1; i <= size; i++)
17       {
18         table[i] = border + Console.ReadLine() + border;
19         for (int j = 1; j <= size; j++)
20         {
21           int cnt;
22           charCount.TryGetValue(table[i][j], out cnt);
23           charCount[table[i][j]] = cnt + 1;
24         }
25       }
26       for (int i = int.Parse(Console.ReadLine()); i > 0; i--)
27       {
28         string word = Console.ReadLine();
29         bool find = CanFind(new Dictionary<char, int>(charCount), word);
30         if (find)
31         {
32           find = false;
33           bool[,] mark = new bool[size + 2, size + 2];
34           for (int x = 1; !find && x <= size; x++)
35             for (int y = 1; !find && y <= size; y++)
36             {
37               if (table[y][x] != word[0]) continue;
38               Array.Clear(mark, 0, mark.Length);
39               find = Search(word, table, mark, y, x, 1); // 深度优先搜索
40             }
41         }
42         Console.WriteLine(word + ": " + (find ? "YES" : "NO"));
43       }
44     }
45 
46     static bool CanFind(Dictionary<char, int> charCount, string word)
47     {
48       foreach (char c in word)
49       {
50         int cnt;
51         charCount.TryGetValue(c, out cnt);
52         if (cnt == 0) return false;
53         charCount[c]--;
54       }
55       return true;
56     }
57 
58     static readonly int[,] direction = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
59 
60     static bool Search(string word, string[] table, bool[,] mark, int y, int x, int depth)
61     {
62       if (mark[y, x]) return false;
63       mark[y, x] = true;
64       if (depth == word.Length) return true;
65       for (int i = 0; i < 4; i++)
66       {
67         int y1 = y + direction[i, 0];
68         int x1 = x + direction[i, 1];
69         if (table[y1][x1] == word[depth] && Search(word, table, mark, y1, x1, depth + 1)) return true;
70       }
71       return mark[y, x] = false;
72     }
73   }
74 }

这两个程序的运行时间如下所示：

可以看出，原来的程序的运行时间为 0.531 秒，改进后的程序的运行时间为 0.125 秒。实际上这道题目的限时是 1.0 秒，也就是说，这个改进其实也是没有什么必要的。原来的程序算法足够简单，速度上也能够满足这道题目时间限制的要求，应该就可以了。