Selectivo 3 - P6

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

struct match{
    int r,c,dir;

    match(){}
    match(int _r, int _c, int _dir):
        r(_r), c(_c), dir(_dir){}
};

#define MAXN 300
#define MAXW 10

int W,N,L[MAXW];
char word[MAXW][MAXN];
char M[MAXN][MAXN + 1];
vector<match> v[MAXW];
int mask[MAXN][MAXN];

int dr[] = {-1,-1,-1,0,0,1,1,1};
int dc[] = {-1,0,1,-1,1,-1,0,1};

bool find_match(int id){
    bool ret = false;
    int len = L[id];

    for(int i = 0;i < N;++i){
        for(int j = 0;j < N;++j){
            for(int k = 0;k < 8;++k){
                bool ok = true;
                int r = i,c = j;

                for(int pos = 0;pos < len && ok;++pos,r += dr[k],c += dc[k])
                    if(r < 0 || c < 0 || r >= N || c >= N || M[r][c] != word[id][pos]) ok = false;

                if(ok){
                    ret = true;
                    v[id].push_back(match(i,j,k));
                    r = i; c = j;

                    for(int pos = 0;pos < len;++pos,r += dr[k],c += dc[k])
                        mask[r][c] |= (1 << id);
                }
            }
        }
    }

    return ret;
}

bool soll;
int M2[MAXN][MAXN];

void search(int id){
    if(id == W){
        soll = true;
        return;
    }

    int len = L[id],r,c,k;

    for(int i = v[id].size() - 1;i >= 0;--i){
        bool ok = true;
        r = v[id][i].r,c = v[id][i].c,k = v[id][i].dir;

        for(int pos = 0;pos < len && ok;++pos,r += dr[k],c += dc[k])
            if(M2[r][c] != -1) ok = false;

        if(ok){
            r = v[id][i].r,c = v[id][i].c;

            for(int pos = 0;pos < len;++pos,r += dr[k],c += dc[k])
                M2[r][c] = id;

            search(id + 1);
            if(soll) return;

            r = v[id][i].r,c = v[id][i].c;

            for(int pos = 0;pos < len;++pos,r += dr[k],c += dc[k])
                M2[r][c] = -1;
        }
    }
}

int main(){
    int tc = 1;
    char aux[2];

    while(true){
        scanf("%d %d",&W,&N);
        if(W == 0) break;

        for(int i = 0;i < W;++i){
            scanf("%s",word[i]);
            L[i] = strlen(word[i]);
        }

        for(int i = 0;i < N;++i){
            for(int j = 0;j < N;++j){
                scanf("%s",aux);
                M[i][j] = aux[0];
            }
        }

        memset(mask,0,sizeof mask);
        bool found = true;

        for(int i = 0;i < W;++i){
            v[i].clear();
            found = found && find_match(i);
        }

        printf("Puzzle %d: ",tc++);

        soll = false;

        if(found){
            memset(M2,-1,sizeof M2);
            search(0);
        }

        bool chall = false;

        for(int i = 0;i < N;++i)
            for(int j = 0;j < N;++j)
                if(__builtin_popcount(mask[i][j]) > 1)
                    chall = true;

        printf("%s\n%s %s\n",chall && soll? "ACCEPT" : "REJECT",found && chall? "YES" : "NO",soll? "YES" : "NO");

    }

    return 0;
}