携程 决赛 第一题 Crossword

//真是郁闷的一晚上
//比赛时看到这题是就感觉会做，感觉思路清晰 就去准备找第二题 ，因为感觉第二题是个经典问题，（我不会计算几何），就去搜索了下，然后找到求最小面积的，改来改去，一直Wa
// 然后就只剩下一个小时了 ，我决定放弃它，去写第一题 就是这题，然后整栋楼离奇断网什么的、、还调试了好久、、

// 思路 :将K个字符串算出Hash值 保存，同时要记录串的长度
//     这样在搜索时候 就可以根据Hash和字符串长度来筛选出某一位置可以填哪些串 因为串的起始和结束位置也能判断可以填的串可以多长
//     这样就是暴力搜索了
//   我对M个串位置进行了排序，然后我发现排不排序都一样，无所谓的

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<iostream>

#include<algorithm>

#include<functional>

#include<cmath>

#include <vector>

using namespace std;

vector <string> Hs[];

vector <int > len[];

int Map[][];

int n,m;

struct node

{

    int x1,y1,x2,y2,k;

    bool operator <(const node&t) const

    {

        if(x1==t.x1) return x2<t.x2;

        return x1<t.x1;

    }

} st[];

int K;

int flag;

char str[];

int ar[];

void dfs(int index)

{

    if(index==m)

    {

        flag=;

        return ;

    }

    int x1=st[index].x1,x2=st[index].x2;

    int y1=st[index].y1,y2=st[index].y2;

    int k=st[index].k;

    int le=x1-x2+y1-y2;

    if(le<) le=-le;

    le++;

    for(int i=; i<Hs[k].size(); i++)

        if(le==len[k][i])

        {

            if(x1==x2)

            {

                int dir=y1<y2?:-;

                int j,id=;

                for(j=y1; j!=y2; id++, j+=dir)

                    if(Map[x1][j]&&Map[x1][j]!=Hs[k][i][id])

                        break;

                if(j==y2)

                {

                    id=;

                    for(j=y1; j!=y2; id++, j+=dir)

                        if(!Map[x1][j])

                        {

                            Map[x1][j]=Hs[k][i][id];

                            ar[j]=;

                        }

                        else

                            ar[j]=;

                      if(!Map[x1][j])

                        {

                            Map[x1][j]=Hs[k][i][id];

                            ar[j]=;

                        }

                        else

                            ar[j]=;

                    dfs(index+);

                    if(flag) return;

                    for(j=y1; j!=y2; j+=dir)

                        if(ar[j])

                            Map[x1][j]=;

                }

            }

            else if(y1==y2)

            {

                int dir=x1<x2?:-;

                int j,id=;

                for(j=x1; j!=x2; id++, j+=dir)

                    if(Map[j][y1]&&Map[j][y1]!=Hs[k][i][id]) break;

                if(j==x2)

                {

                    id=;

                    for(j=x1; j!=x2; id++,j+=dir)

                        if(!Map[j][y1])

                        {

                            Map[j][y1]=Hs[k][i][id];

                            ar[j]=;

                        }

                        else

                            ar[j]=;

                     if(!Map[j][y1])

                        {

                            Map[j][y1]=Hs[k][i][id];

                            ar[j]=;

                        }

                        else

                            ar[j]=;

                    dfs(index+);

                    if(flag) return;

                    for(j=x1; j!=x2; j+=dir)

                        if(ar[j])

                            Map[j][y1]=;

                }

            }

        }

}

int main()

{

    int i,j;

    int Case=;

    while(scanf("%d %d",&n,&m),n|m)

    {

        if(Case++!=) printf("\n");

        for(i=; i<m; i++)

            scanf("%d %d %d %d %d",&st[i].x1,&st[i].y1,&st[i].x2,&st[i].y2,&st[i].k);

        sort(st,st+m);

        scanf("%d",&K);

        for(i=; i<K; i++)

        {

            scanf("%s",str);

            int hs=;

            for(j=; str[j]!='\0'; j++)

                hs=(hs*+str[j])%;

            Hs[hs].push_back(str);

            len[hs].push_back(j);

        }

        memset(Map,,sizeof(Map));

        flag=;

        dfs();

        if(flag)

            for(i=; i<=n; i++)

            {

                for(j=; j<n; j++)

                    if(Map[i][j])

                        printf("%c",Map[i][j]);

                    else

                        printf(" ");

                if(Map[i][j])

                    printf("%c\n",Map[i][j]);

                else

                    printf(" \n");

            }

    }

    return ;

}