Isabella's Message
Time Limit: 20 Sec Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=4119
Description
Isabella and Steve are very good friends, and they often write letters to each other. They exchange funny experiences, talk about people around, share their feelings and write about almost everything through the letters. When the letters are delivered, they are quite afraid that some other people(maybe their parents) would peek. So they encrypted the letter, and only they know how to decrypt it. This guarantees their privacy.
The encrypted message is an N * N matrix, and each grid contains a character.
Steve
uses a special mask to work as a key. The mask is N * N(where N is an
even number) matrix with N*N/4 holes of size 1 * 1 on it.
The decrypt process consist of the following steps:
1. Put the mask on the encrypted message matrix
2. Write down the characters you can see through the holes, from top to down, then from left to right.
3. Rotate the mask by 90 degrees clockwise.
4. Go to step 2, unless you have wrote down all the N*N characters in the message matrix.
5. Erase all the redundant white spaces in the message.
For
example, you got a message shown in figure 1, and you have a mask looks
like figure 2. The decryption process is shown in figure 3, and finally
you may get a message "good morning".
You
can assume that the mask is always carefully chosen that each character
in the encrypted message will appear exactly once during decryption.
However, in the first step of decryption, there are several ways to
put the mask on the message matrix, because the mask can be rotated
(but not flipped). So you may get different results such as "od morning
go" (as showed in figure 4), and you may also get other messages like
"orning good m", "ng good morni".
Steve
didn't know which direction of the mask should be chosen at the
beginning, but after he tried all possibilities, he found that the
message "good morning" is the only one he wanted because he couldn't
recognize some words in the other messages. So he will always consider
the message he can understand the correct one. Whether he can understand
a message depends whether he knows all the words in the message. If
there are more than one ways to decrypt the message into an
understandable one, he will choose the lexicographically smallest one.
The way to compare two messages is to compare the words of two messages
one by one, and the first pair of different words in the two messages
will determine the lexicographic order of them.
Isabella sends
letters to Steve almost every day. As decrypting Isabella's message
takes a lot of time, and Steve can wait no longer to know the content of
the message, he asked you for help. Now you are given the message he
received, the mask, and the list of words he already knew, can you write
a program to help him decrypt it?
The encrypted message is an N * N matrix, and each grid contains a character.
Steve
uses a special mask to work as a key. The mask is N * N(where N is an
even number) matrix with N*N/4 holes of size 1 * 1 on it.
The decrypt process consist of the following steps:
1. Put the mask on the encrypted message matrix
2. Write down the characters you can see through the holes, from top to down, then from left to right.
3. Rotate the mask by 90 degrees clockwise.
4. Go to step 2, unless you have wrote down all the N*N characters in the message matrix.
5. Erase all the redundant white spaces in the message.
For
example, you got a message shown in figure 1, and you have a mask looks
like figure 2. The decryption process is shown in figure 3, and finally
you may get a message "good morning".
You
can assume that the mask is always carefully chosen that each character
in the encrypted message will appear exactly once during decryption.
However, in the first step of decryption, there are several ways to
put the mask on the message matrix, because the mask can be rotated
(but not flipped). So you may get different results such as "od morning
go" (as showed in figure 4), and you may also get other messages like
"orning good m", "ng good morni".
Steve
didn't know which direction of the mask should be chosen at the
beginning, but after he tried all possibilities, he found that the
message "good morning" is the only one he wanted because he couldn't
recognize some words in the other messages. So he will always consider
the message he can understand the correct one. Whether he can understand
a message depends whether he knows all the words in the message. If
there are more than one ways to decrypt the message into an
understandable one, he will choose the lexicographically smallest one.
The way to compare two messages is to compare the words of two messages
one by one, and the first pair of different words in the two messages
will determine the lexicographic order of them.
Isabella sends
letters to Steve almost every day. As decrypting Isabella's message
takes a lot of time, and Steve can wait no longer to know the content of
the message, he asked you for help. Now you are given the message he
received, the mask, and the list of words he already knew, can you write
a program to help him decrypt it?
Input
The first line contains an integer T(1 <= T <= 100), indicating the number of test cases.
Each test case contains several lines.
The first line contains an even integer N(2 <= N <= 50), indicating the size of the matrix.
The
following N lines each contains exactly N characters, reresenting the
message matrix. The message only contains lowercase letters and
periods('.'), where periods represent the white spaces.
You can assume the matrix contains at least one letter.
The
followingN lines each containsN characters, representing the mask
matrix. The asterisk('*') represents a hole, and period('.') otherwise.
The next line contains an integer M(1 <= M <= 100), the number of
words he knew.
Then the following M lines each contains a string
represents a word. The words only contain lowercase letters, and its
length will not exceed 20.
Output
For each test case in the input, print one line: "Case #X: Y", where X is the test case number (starting with 1) and Y is Isabella's message.
If Steve cannot understand the message, just print the Y as "FAIL TO DECRYPT".
Sample Input
3 4 o.do .ng. grmn o.i. .*.. *.*. .... *... 2 good morning 4 ..lf eoyv oeou vrer ..*. .*.. .... *.*. 5 i you the love forever 4 .sle s.c. e.fs ..uu *... .*.. ...* ..*. 1 successful
Sample Output
Case #1: good morning Case #2: love you forever Case #3: FAIL TO DECRYPT
HINT
题意
给你一个n*n的格子，格子里面有字母和空格，然后你拿挡板去截取字母，然后问你是否能够还原。
题解：
最多4种情况，直接模拟搞就好了
我的代码是wa的，我不想再写了= =
代码：
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 10001
#define mod 10007
#define eps 1e-9
int Num;
char CH[];
//const int inf=0x7fffffff; //нчоч╢С
const int inf=0x3f3f3f3f;
/* inline void P(int x)
{
Num=0;if(!x){putchar('0');puts("");return;}
while(x>0)CH[++Num]=x%10,x/=10;
while(Num)putchar(CH[Num--]+48);
puts("");
}
*/
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void P(int x)
{
Num=;if(!x){putchar('');puts("");return;}
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);
puts("");
}
//************************************************************************************** string s1[maxn];
string s2[maxn];
string s3[maxn];
int n,m;
string s66[maxn];
int flag;
int cnt;
int deal(string s55)
{
//cout<<s55<<endl;
cnt=;
flag=;
s66[cnt]="";
for(int i=;i<s55.size();i++)
{
if(s55[i]=='.')
continue;
else
{
s66[cnt]+=s55[i];
if(i+>=s55.size()||s55[i+]=='.')
{
int flag2=;
for(int i=;i<m;i++)
if(s66[cnt]==s3[i])
flag2++;
if(!flag2)
flag=;
if(flag==)
break;
cnt++;
s66[cnt]="";
}
}
}
return flag;
}
int main()
{
//freopen("test.txt","r",stdin);
int t=read();
for(int cas=;cas<=t;cas++)
{
//memset(s1,0,sizeof(s1));
//memset(s2,0,sizeof(s2));
//memset(s3,0,sizeof(s3));
n=read();
for(int i=;i<n;i++)
cin>>s1[i];
int len=s1[].size();
for(int i=;i<n;i++)
cin>>s2[i];
m=read();
for(int i=;i<m;i++)
{
cin>>s3[i];
}
string s11,s22,s33,s44;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
if(s2[i][j]=='*')
s11+=s1[i][j];
if(s2[j][n-i-]=='*')
s44+=s1[i][j];
if(s2[n-i-][n-j-]=='*')
s33+=s1[i][j];
if(s2[n-j-][i]=='*')
s22+=s1[i][j];
}
}
string s55=s11+s22+s33+s44;
deal(s55);
if(!flag)
{
printf("Case #%d: ",cas);
for(int i=;i<cnt;i++)
{
if(i!=cnt-)
cout<<s66[i]<<" ";
else
cout<<s66[i];
}
cout<<endl;
}
else
{
s55=s22+s33+s44+s11;
deal(s55);
if(!flag)
{
printf("Case #%d: ",cas);
for(int i=;i<cnt;i++)
{
if(i!=cnt-)
cout<<s66[i]<<" ";
else
cout<<s66[i];
}
cout<<endl;
}
else
{
s55=s33+s44+s11+s22;
deal(s55);
if(!flag)
{
printf("Case #%d: ",cas);
for(int i=;i<cnt;i++)
{
if(i!=cnt-)
cout<<s66[i]<<" ";
else
cout<<s66[i];
}
cout<<endl;
}
else
{
s55=s44+s11+s22+s33;
deal(s55);
if(!flag)
{
printf("Case #%d: ",cas);
for(int i=;i<cnt;i++)
{
if(i!=cnt-)
cout<<s66[i]<<" ";
else
cout<<s66[i];
}
cout<<endl;
}
else
{
printf("Case #%d: FAIL TO DECRYPT\n",cas);
}
}
}
}
}
}