Alex 喜歡填詞游戲。填詞游戲是一個非常簡單的游戲。填詞游戲包括一個 N * M 大小的矩形方格盤和 P 個單詞。然后需要把每個方格中填上一個字母使得每個單詞都能在方格盤上被找到。每個單詞都能被找到要滿足下面的條件： 每個方格都不能同時屬于超過一個的單詞。一個長為 k 的單詞一定要占據 k 個方格。單詞在方格盤中出現的方向只能是豎直的或者水平的（可以由豎直轉向水平，反之亦然）。 你的任務是首先在方格盤上找到所有的單詞，當然在棋盤上可能有些方格沒有被單詞占據。然后把這些沒有用的方格找出來，把這些方格上的字母按照字典序組成一個“神秘單詞”。 如果你還不了解規則，我們可以用一個例子來說明，比如在下圖中尋找單詞 BEG 和GEE。
輸入的第一行包括三個整數 N， M 和 P (2 <= M, N <= 10, 0 <= P <=100)。接下來的 N 行，每行包括 M 個字符，來表示方格盤。接下來 P 行給出需要在方格盤中找到的單詞。 輸入保證填詞游戲至少有一組答案。 輸入中給出的字母都是大寫字母。
輸出“神秘單詞”，注意“神秘單詞”中的字母要按照字典序給出。
3 3 2EBGGEEEGEBEGGEE輸出樣例
EEG解題思路
題目中給出的條件比較隱晦。輸入中給出的字母都是大寫字母 – 表明輸出也只能是大寫字母。輸入保證填詞游戲至少有一組答案 – 這說明我們不必尋找單詞所在的位置，只要去掉這些單詞所占用的字母就可以了。 “神秘單詞”中的字母要按照字典序給出 – 說明我們只要知道“神秘單詞”中的字母組成就可以了，在字母組成確定的情況下，按字典序輸出的方式只有一種。分析到這里我們發現這其實是個很簡單的問題。給出一個字母的集合，從中去掉一些在給出單詞中出現過的字母，將剩下的字母按字典序輸出！ 可以定義一個有 26 個元素的數組，分別記錄在輸入的矩形中，每個字母出現的次數，當讀入單詞時，將數組中對應到單詞中的字母的元素值減一。處理完所有的單詞后，將數組中的非 0 的元素對應的字母依次輸出，數組元素的值是幾，就輸出幾次該字母。
參考程序
#include <iostream>#include <cstdio>using namespace std;int main(){ int characters[26]; int n,m,p; int i,j; for(i=0;i<26;i++){ characters[i]=0; } cin>>n>>m>>p; //讀入 n*m 的矩陣，并記錄矩陣中每個字母出現的次數 for(i=0;i<n;i++){ char str[11]; cin>>str; for(j=0;str[j]!='/0';j++){ characters[str[j]-'A']++; } } //讀入 p 個單詞，并且將單詞中出現的字母在上一段的累計數組中去掉 for(i=0;i<p;i++){ char str[200]; cin>>str; for(j=0;str[j]!='/0';j++){ characters[str[j]-'A']--; } } //輸出所有出現次數大于 0 的字母。 for(i=0;i<26;i++){ if(characters[i]){ for(j=0;j<characters[i];j++){
新聞熱點
疑難解答
