学步园

题目请戳这里

题目大意：给一个n*n的矩阵，n为偶数，矩阵由小写字母和'.'组成，'.'表示空格，再给一个n*n矩阵，由'.'和'*'组成，'*'表示洞，'.'表示障碍。现在将2张卡片重合，将能看到的字符从上往下从左往右依次取出组成一个新单词。卡片可以顺时针旋转90度，再取出能看到的单词，一共有4个单词，4个单词再依次组成一个句子，因为卡片是连续转动的，所以4个单词首尾相连，任取一个做句子头，所以句子一共也是4个。再给m个单词，求出字典序最小的句子并要求句子中每个单词都在给定的m个单词中。

题目分析：简单模拟题。比赛的时候都看错了题目。。。最后还兴致勃勃的敲起了字典树。。。没看到空格。。。如果算空格的话就比较简单了。将组成的句子中单词一一挑出来，在给定的m个单词中找就ok了。

详情请见代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 55;
map<string,int>lcm;
char s[N][N];
int num;
struct msk
{
    int x,y;
}mask[1000];
int n,m;
int cmp(struct msk a,struct msk b)
{
    if(a.x != b.x)
        return a.x < b.x;
    else
        return a.y < b.y;
}
int cmp1(string a,string b)
{
    int i,j;
    i = j = 0;
    while(a[i] == '.')
        i ++;
    while(b[j] == '.')
        j ++;
    while(i < a.length() && j < b.length())
    {
        if(a[i] == b[j])
            i ++,j ++;
        else
            return a[i] < b[j];
    }
}
void Rotate()
{
    for(int i = 1;i < num;i ++)
    {
        int t= mask[i].x;
        mask[i].x = mask[i].y;
        mask[i].y = n - t - 1;
    }
    sort(mask + 1,mask + num,cmp);
}
int main()
{
    int t,cas;
    int i,j;
    cas = 0;
    scanf("%d",&t);
    while(t --)
    {
        scanf("%d",&n);
        gets(s[0]);
        for(i = 0;i < n;i ++)
            gets(s[i]);
        num = 1;
        for(i = 0;i < n;i ++)
        {
            for(j = 0;j < n;j ++)
            {
                if(getchar() == '*')
                {
                    mask[num].x = i;
                    mask[num ++].y = j;
                }
            }
            getchar();
        }
        scanf("%d",&m);
        lcm.clear();
        string word;
        for(i = 0;i < m;i ++)
        {
            cin>>word;
            lcm[word] = 1;
        }
        string str[4];
        for(i = 0;i < 4;i ++)
            str[i] = "";
        for(i = 0;i < 4;i ++)
        {
            for(j = 1;j < num;j ++)
                str[i] += s[mask[j].x][mask[j].y];
            Rotate();
        }
        string ans[4];
        for(i = 0;i < 4;i ++)
        {
            for(j = 0;j < 4;j ++)
                ans[i] += str[(i + j)%4];
        }
//        for(i = 0;i < 4;i ++)
//            cout<<ans[i]<<endl;
//        cout<<endl;
        sort(ans,ans + 4,cmp1);
//        for(i = 0;i < 4;i ++)
//            cout<<ans[i]<<endl;
        string tmp;
        bool flag;
        vector<string> out;
        for(i = 0;i < 4;i ++)
        {
            flag = true;
            out.clear();
            j = 0;
            while(j < ans[i].length())
            {
                while(j < ans[i].length() && ans[i][j] == '.') j ++;
                if(j >= ans[i].length())
                    break;
                tmp = "";
                while(j < ans[i].length() && ans[i][j] != '.')
                    tmp += ans[i][j],j ++;
                if(lcm[tmp] == 0)
                {
                    flag = false;
                    break;
                }
                else
                {
                    out.push_back(tmp);
                    //j ++;
                }
            }
            if(flag)
                break;
        }
        printf("Case #%d:",++cas);
        if(i < 4)
        {
            for(j = 0;j < out.size();j ++)
                cout<<" "<<out[j];
            cout<<endl;
        }
        else
            puts(" FAIL TO DECRYPT");
    }
    return 0;
}
//31MS	324K