首页 > ACM题库 > HDU-杭电 > HDU 4119-Isabella’s Message-模拟-[解题报告]HOJ
2015
04-16

HDU 4119-Isabella’s Message-模拟-[解题报告]HOJ

Isabella’s Message

问题描述 :

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".
Holiday's Accommodation

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".
Holiday's Accommodation

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 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.

输出:

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.

样例输入:

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

样例输出:

Case #1: good morning
Case #2: love you forever
Case #3: FAIL TO DECRYPT

题目链接:Click here~~

题意:

有一个 n*n 的单词表,里面写有字母或者空格。然后给你一个 n*n 的不透明纸板,纸板中有若干洞,把纸板盖到单词表上,你可以从洞里看到一些单词,按照顺序读出来,然后旋转90度,继续,直到转完一圈。最后问将它们连起来是否能组成一句话,使句中单词都在他的字典里。

解题思路:

初始方向不定,但最多就 4 种情况,可以枚举。之后就是字符串模拟了。

#include <set>
#include <string>
#include <stdio.h>
#include <algorithm>
using namespace std;

struct Point
{
    int x,y;
    Point(){}
    Point(int x,int y):x(x),y(y){}
    bool operator <(const Point& S)const
    {
        return x<S.x || x==S.x && y<S.y;
    }
}P[4][666];

struct TT
{
    string s;
    bool ok;
    bool operator <(const TT& S)const
    {
        return s < S.s;
    }
}Ans[4];

int n,m;

Point Rotary(Point A)
{
    return Point(A.y,n+1-A.x);
}

int main()
{
    int z,ncase=0;
    char tmp[25],map[55][55];
    set<string> Dic;
    scanf("%d",&z);
    while(z--)
    {
        Dic.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%s",map[i]+1);
        int top = 0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",map[0]+1);
            for(int j=1;j<=n;j++)
                if(map[0][j] == '*')
                    P[0][top++] = Point(i,j);
        }
        for(int i=1;i<=3;i++)
            for(int j=0;j<top;j++)
                P[i][j] = Rotary(P[i-1][j]);
        for(int i=0;i<=3;i++)
            sort(P[i],P[i]+top);
        for(int k=0;k<=3;k++)
            Ans[k].ok = true;
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%s",tmp);
            Dic.insert(tmp);
        }
        for(int k=0;k<=3;k++)
        {
            int loc = -1;
            string& str = Ans[k].s;
            str = "";
            for(int i=k;i<k+4;i++)
                for(int j=0;j<top;j++)
                {
                    char ttmp = map[ P[i%4][j].x ][ P[i%4][j].y ];
                    str += ttmp=='.' ? ' ' : ttmp;
                }
            while(!str.empty() && str[0]==' ')
                str.erase(str.begin());
            for(int i=1;i<str.length();i++)
                if(str[i]==' ' && str[i-1]==' ')
                    str.erase(str.begin()+(i--));
            if(!str.empty() && str[ str.length()-1 ]==' ')
                str.erase(str.end()-1);
            if(str.empty())
            {
                Ans[k].ok = false;
                continue;
            }
            while(++loc < str.length())
            {
                string word;
                while(loc<str.length() && str[loc]!=' ')
                    word += str[loc++];
                if(Dic.find(word) == Dic.end())
                {
                    Ans[k].ok = false;
                    break;
                }
            }
        }
        sort(Ans,Ans+4);
        printf("Case #%d: ",++ncase);
        int i;
        for(i=0;i<4;i++)
            if(Ans[i].ok)
            {
                puts(Ans[i].s.c_str());
                break;
            }
        if(i == 4)
            puts("FAIL TO DECRYPT");
    }
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dgq8211/article/details/8069045


  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。