0006-填词

问题描述

Alex 喜欢填词游戏。填词游戏是一个非常简单的游戏。填词游戏包括一个 N * M 大小的矩形方格盘和 P 个单词。然后需要把每个方格中填上一个字母使得每个单词都能在方格盘上被找到。每个单词都能被找到要满足下面的条件:
* 一个长为 k 的单词一定要占据 k 个方格。
* 每个方格都不能同时属于超过一个的单词。
* 单词在方格盘中出现的方向只能是竖直的或者水平的(可以由竖直转向水平,反之亦然)。
你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后把这些没有用的方格找出来，把这些方格上的字母按照字典序组成一个“神秘单词”。 如果你还不了解规则,我们可以用一个例子来说明,比如在下图中寻找单词 BEG 和 GEE。

0006-填词.png

输入

输入的第一行包括三个整数 N、M和 P (2 <= M, N <= 10, 0 <= P <=100)。接下来的 N 行，每行包括 M 个字符，来表示方格盘。接下来 P 行给出需要在方格盘中找到的单词。 输入保证填词游戏至少有一组答案。 输入中给出的字母都是大写字母。

输出

输出“神秘单词”,注意“神秘单词”中的字母要按照字典序给出

输入样列

3 3 2
EBG
GEE
EGE
BEG
GEE

输出样例

EEG

算法实现

using System;

namespace Questions{
    class Program{
        static void Main(string[] args){
           //输入N M P
            string input = Console.ReadLine();
            //格式转换
            string[] str = input.Split(' ');
            int n = int.Parse(str[0]);
            int m = int.Parse(str[1]);
            int p = int.Parse(str[2]);
            int[] num = new int[26];
            if (p >= 0 && p <= 100 && m >= 2 && m <= 10 && n >= 2 && n <= 10){
                //解题思路：不用去找到每个字符串，因为输入给出的字符串是必然会找到的，所以说，我们的任务只是输出剩下的字母，因此，只需用一个整型数组character[26]来记录字母出现的次数并输出即可
                for (int i = 0; i < n; i++){
                    input = Console.ReadLine();//输入n行m列字符
                    for (int j = 0; j < m; j++) {
                        num[input[j] - 'A']++;
                    }
                }
                for (int i = 0; i < p; i++){
                    input = Console.ReadLine();//输入
                    for (int j = 0; j < input.Length; j++)
                        num[input[j] - 'A']--;
                 }
                for (int i = 0; i < 26; i++)
                    for (int j = 0; j < num[i]; j++)
                        Console.Write("{0}",(char)('A'+i));
                Console.WriteLine();
            }
            Console.ReadKey();
        }
    }
}