2801:填词
时间限制:
1000ms
内存限制:
65536kB
描述
Alex喜欢填词游戏。填词是游戏是一个非常简单的游戏。填词游戏包括一个N * M大小的矩形方格盘和P个单词。玩家需要把每个方格中填上一个字母使得每个单词都能在方格盘上找到。每个单词都能找到要满足下面的条件：
每个方格都不能同时属于超过一个的单词。一个长为k的单词一定要占据k个方格。单词在方格盘中出现的方向只能是竖直的或者水平的。
你的任务是首先在方格盘上找到所有的单词，当然在棋盘上可能有些方格没有被单词占据。然后把这些没有用的方格找出来，把这些方格上的字母按照字典序组成一个“神秘单词”。
如果你还不了解规则，我们可以具一个例子，比如在下图中寻找单词BEG和GEE。
输入
输入的第一行包括三个整数N，M和P (2 <= M, N <= 10, 0 <= P <=100)。接下来的N行，每行包括M个字符，来表示方格盘。接下来P行给出需要在方格盘中找到的单词。
输入保证填词游戏至少有一组答案。//于是可以利用26位的数组记录各个字母个数即可,当个数为0时最后不输出(不算进”神秘单词”中)即可
输入中给出的字母都是大写字母。
输出
输出“神秘单词”，注意“神秘单词”中的字母要按照字典序给出。
样例输入
3 3 2
EBG
GEE
EGE
BEG
GEE
样例输出
EEG
#include"iostream"
using namespace std;
int main()
{
int N,M,P;
cin>>N>>M>>P;
//建立矩阵
char** matrix=new char*[N];
for(int i=0;i<M;i++)
matrix[i]=new char[M];
//输入矩阵
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
{
cin>>matrix[i][j];
}
//用26位数组记录matrix字母个数
int num[26];
//memset(num,0,sizeof(num));
for(int k=0;k<26;k++)
{
num[k]=0;
}
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
{
num[matrix[i][j]-'A']++;
}
//Test function
//根据给出的P行字母排除非"神秘单词"有的字母
char p[101];
for(int i=0;i<P;i++)
{
cin>>p;
int j=0;
while(p[j]!='\0')
{
num[p[j]-'A']--;//num的元素最小就是0,不可能为负数
j++;
}
}
for(int i=0;i<26;i++)
{
while(num[i]--)
{
cout<<(char)(i+'A');
}
}
cout<<endl;
return 0;
}