BOJ/Platinum ~ Diamond

[BOJ/Diamond 5] 백준 6300 단어 퍼즐(C++)

보단잉 2023. 5. 2. 13:11

문제 링크

 

문제

긴말이 필요없다. 단어 퍼즐을 풀어보자.

직사각형 모양의 격자판에서  각 단어들이 상하, 좌우, 대각선 총 8개의 방향 중 하나로 연속해서 등장하는 위치를 찾아야 한다(문제의 예를 보고 싶다면 원문 또는 예제 입력을 참조하시오).

제일 왼쪽 위 칸의 위치는 (0, 0)이다. 이제 각 단어가 등장하는 시작 위치를 찾고, 어느 방향으로 읽어야 하는지도 구하시오. 각 방향은 북쪽 방향부터 시계방향으로 A~H라고 표기한다.

입력

첫째 줄에 격자판의 줄 수 L, 열 수 C, 찾아야 할 단어의 개수 W가 주어진다(0 < L, C, W ≤ 1000).

이어서 L개의 줄에 격자판이 주어지며 각 줄은 C글자의 대문자로 이루어져 있다.

이어서 W개의 줄에 찾아야 할 각 단어가 주어지며, 각 단어는 대문자로 이루어져 있다. 주어지는 단어는 반드시 격자판에 존재한다.

출력

W개의 줄에 거쳐서 각 단어가 등장하는 시작 위치의 줄 번호와 열 번호, 그리고 읽어야 하는 방향을 A~H 사이의 문자 하나로 공백으로 구분지어 출력한다.

단어가 여러 곳에서 등장할 경우,

  • 행 위치가 더 작거나,
  • 행 위치가 같으면 열 위치가 더 작거나,
  • 행과 열 위치가 같으면 방향이 작은(A~H까지의 방향이 있다면 A가 가장 작습니다)

위치를 출력해야 한다.

예제 입력 1

20 20 10
QWSPILAATIRAGRAMYKEI
AGTRCLQAXLPOIJLFVBUQ
TQTKAZXVMRWALEMAPKCW
LIEACNKAZXKPOTPIZCEO
FGKLSTCBTROPICALBLBC
JEWHJEEWSMLPOEKORORA
LUPQWRNJOAAGJKMUSJAE
KRQEIOLOAOQPRTVILCBZ
QOPUCAJSPPOUTMTSLPSF
LPOUYTRFGMMLKIUISXSW
WAHCPOIYTGAKLMNAHBVA
EIAKHPLBGSMCLOGNGJML
LDTIKENVCSWQAZUAOEAL
HOPLPGEJKMNUTIIORMNC
LOIUFTGSQACAXMOPBEIO
QOASDHOPEPNBUYUYOBXB
IONIAELOJHSWASMOUTRK
HPOIYTJPLNAQWDRIBITG
LPOINUYMRTEMPTMLMNBO
PAFCOPLHAVAIANALBPFS
MARGARITA
ALEMA
BARBECUE
TROPICAL
SUPREMA
LOUISIANA
CHEESEHAM
EUROPA
HAVAIANA
CAMPONESA

예제 출력 1

0 15 G
2 11 C
7 18 A
4 8 C
16 13 B
4 15 E
10 3 D
5 1 E
19 7 C
11 11 H

알고리즘 분류

  • 구현
  • 트라이
  • kmp

풀이

W개의 단어에 먼저 번호를 매긴다. 그리고 단어들을 트라이에 insert하고, 단어의 끝 노드에는 해당 단어의 번호를 기록한다. 그리고 실패 함수를 통해 각 노드의 Fail Link를 연결한다.

이제 격자판에 W개의 단어를 모두 찾을 것이다. 단어는 전부 격자판 안에 존재한다는 게 보장된다.

이제 격자판을 8방향 탐색을 통해 단어를 찾아준다. 8방향의 알파벳은 북쪽부터 시계 방향으로 A부터 H까지이다.

kmp를 통해 탐색해주면서 번호가 기록된 노드, 즉 특정 단어의 끝을 찾았다면, 해당 단어를 찾은 것인지 찾지 않은 것인지를 확인한다.

그것을 확인하는 방법은, 현재 칸의 좌표를 적절히 조절하여 단어의 처음 문자라고 추정되는 칸까지 온 후 해당 칸의 문자가 격자판 안에 존재하는지, 그리고 추정되는 단어의 첫 번째 문자인지를 확인한다. 모든 조건이 만족한다면 해당 단어를 찾은 것이다.

하지만 해당 단어가 격자판의 여러 군데에 존재할 수 있다. 이런 경우, 행, 열, 그리고 방향을 비교해서 더 작은 값으로 설정한다.

이렇게 격자판의 8방향을 모두 탐색해서 W개의 단어의 각각의 첫 번째 문자의 위치와, 탐색해야 할 방향을 전부 구하고 각각의 좌표와 방향을 공백으로 구분하여 출력해준다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct TRIE {
    int isEnd;
    vector<pair<char, TRIE*> > Child;
    TRIE* Fail;

    TRIE() {
        isEnd = -1;
        Child.clear();
        Fail = nullptr;
    }

    void insert_Pattern(string Pattern, int Index) {
        TRIE* NowTrie = this;

        for (int i = 0; i < Pattern.size(); i++) {
            char Now = Pattern[i];

            bool Flag = false;
            for (auto& A : NowTrie->Child) {
                if (A.first == Now) {
                    Flag = true;
                    NowTrie = A.second;
                    break;
                }
            }
            if (!Flag) {
                NowTrie->Child.push_back(make_pair(Now, new TRIE));
                NowTrie = NowTrie->Child.back().second;
            }
        }
        NowTrie->isEnd = Index;
    }

    void find_Fail() {
        TRIE* Root = this;
        queue<TRIE*> Q;
        Q.push(Root);

        while (!Q.empty()) {
            TRIE* NowTrie = Q.front();
            Q.pop();

            for (auto& IT : NowTrie->Child) {
                TRIE* NextTrie = IT.second;
                if (NowTrie == Root) {
                    NextTrie->Fail = Root;
                }
                else {
                    TRIE* PrevTrie = NowTrie->Fail;
                    while (PrevTrie != Root) {
                        bool Flag = false;
                        for (auto A : PrevTrie->Child) {
                            if (A.first == IT.first) {
                                Flag = true;
                                break;
                            }
                        }
                        if (Flag) {
                            break;
                        }
                        PrevTrie = PrevTrie->Fail;
                    };
                    for (auto A : PrevTrie->Child) {
                        if (A.first == IT.first) {
                            PrevTrie = A.second;
                            break;
                        }
                    }
                    NextTrie->Fail = PrevTrie;
                }
                if (NextTrie->Fail->isEnd >= 0) {
                    if (NextTrie->isEnd == -1) {
                        NextTrie->isEnd = NextTrie->Fail->isEnd;
                    }
                }
                Q.push(NextTrie);
            }
        };
    }
};

struct INFO {
    int Y, X;
    char Dir;
};

int L, C, W;
string S;
char MAP[MAX][MAX];
vector<string> Word;
int Word_Length[MAX];
int MoveY[8] = { -1,-1,0,1,1,1,0,-1 };
int MoveX[8] = { 0,1,1,1,0,-1,-1,-1 };
vector<INFO> Answer;

void kmp(TRIE* Root) {
    // 1. C
    for (int i = 0; i < L; i++) {
        TRIE* NowTrie = Root;
        for (int j = 0; j < C; j++) {
            char Now = MAP[i][j];

            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = i;
                int FirstX = j - (MoveX[2] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'C') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'C';
                    }
                }
            }
        }
    }

    // 2. E
    for (int i = 0; i < C; i++) {
        TRIE* NowTrie = Root;
        for (int j = 0; j < L; j++) {
            char Now = MAP[j][i];

            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = j - (MoveY[4] * NowL);
                int FirstX = i;
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'E') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'E';
                    }
                }
            }
        }
    }

    // 3. G
    for (int i = 0; i < L; i++) {
        TRIE* NowTrie = Root;
        for (int j = (C - 1); j >= 0; j--) {
            char Now = MAP[i][j];

            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = i;
                int FirstX = j - (MoveX[6] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'G') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'G';
                    }
                }
            }
        }
    }

    // 4. A
    for (int i = 0; i < C; i++) {
        TRIE* NowTrie = Root;
        for (int j = (L - 1); j >= 0; j--) {
            char Now = MAP[j][i];

            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = j - (MoveY[0] * NowL);
                int FirstX = i;
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'A') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'A';
                    }
                }
            }
        }
    }

    // 5. B
    for (int i = 0; i < L; i++) {
        TRIE* NowTrie = Root;
        int NowY = i;
        int NowX = 0;
        while (1) {
            if ((NowY < 0) || (NowY >= L) || (NowX < 0) || (NowX >= C)) {
                break;
            }

            char Now = MAP[NowY][NowX];
            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = NowY - (MoveY[1] * NowL);
                int FirstX = NowX - (MoveX[1] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'B') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'B';
                    }
                }
            }
            NowY += MoveY[1];
            NowX += MoveX[1];
        };
    }
    for (int i = 1; i < C; i++) {
        TRIE* NowTrie = Root;
        int NowY = L - 1;
        int NowX = i;
        while (1) {
            if ((NowY < 0) || (NowY >= L) || (NowX < 0) || (NowX >= C)) {
                break;
            }

            char Now = MAP[NowY][NowX];
            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = NowY - (MoveY[1] * NowL);
                int FirstX = NowX - (MoveX[1] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'B') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'B';
                    }
                }
            }
            NowY += MoveY[1];
            NowX += MoveX[1];
        };
    }

    // 6. D
    for (int i = (C - 1); i >= 0; i--) {
        TRIE* NowTrie = Root;
        int NowY = 0;
        int NowX = i;
        while (1) {
            if ((NowY < 0) || (NowY >= L) || (NowX < 0) || (NowX >= C)) {
                break;
            }

            char Now = MAP[NowY][NowX];
            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = NowY - (MoveY[3] * NowL);
                int FirstX = NowX - (MoveX[3] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'D') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'D';
                    }
                }
            }
            NowY += MoveY[3];
            NowX += MoveX[3];
        };
    }
    for (int i = 0; i < L; i++) {
        TRIE* NowTrie = Root;
        int NowY = i;
        int NowX = 0;
        while (1) {
            if ((NowY < 0) || (NowY >= L) || (NowX < 0) || (NowX >= C)) {
                break;
            }

            char Now = MAP[NowY][NowX];
            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = NowY - (MoveY[3] * NowL);
                int FirstX = NowX - (MoveX[3] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'D') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'D';
                    }
                }
            }
            NowY += MoveY[3];
            NowX += MoveX[3];
        };
    }

    // 7. F
    for (int i = 0; i < C; i++) {
        TRIE* NowTrie = Root;
        int NowY = 0;
        int NowX = i;
        while (1) {
            if ((NowY < 0) || (NowY >= L) || (NowX < 0) || (NowX >= C)) {
                break;
            }

            char Now = MAP[NowY][NowX];
            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = NowY - (MoveY[5] * NowL);
                int FirstX = NowX - (MoveX[5] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'F') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'F';
                    }
                }
            }
            NowY += MoveY[5];
            NowX += MoveX[5];
        };
    }
    for (int i = 0; i < L; i++) {
        TRIE* NowTrie = Root;
        int NowY = i;
        int NowX = C - 1;
        while (1) {
            if ((NowY < 0) || (NowY >= L) || (NowX < 0) || (NowX >= C)) {
                break;
            }

            char Now = MAP[NowY][NowX];
            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = NowY - (MoveY[5] * NowL);
                int FirstX = NowX - (MoveX[5] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'F') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'F';
                    }
                }
            }
            NowY += MoveY[5];
            NowX += MoveX[5];
        };
    }

    // 8. H
    for (int i = 0; i < L; i++) {
        TRIE* NowTrie = Root;
        int NowY = i;
        int NowX = C - 1;
        while (1) {
            if ((NowY < 0) || (NowY >= L) || (NowX < 0) || (NowX >= C)) {
                break;
            }

            char Now = MAP[NowY][NowX];
            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = NowY - (MoveY[7] * NowL);
                int FirstX = NowX - (MoveX[7] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'H') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'H';
                    }
                }
            }
            NowY += MoveY[7];
            NowX += MoveX[7];
        };
    }
    for (int i = (C - 1); i >= 0; i--) {
        TRIE* NowTrie = Root;
        int NowY = L - 1;
        int NowX = i;
        while (1) {
            if ((NowY < 0) || (NowY >= L) || (NowX < 0) || (NowX >= C)) {
                break;
            }

            char Now = MAP[NowY][NowX];
            while (NowTrie != Root) {
                bool Flag = false;
                for (auto A : NowTrie->Child) {
                    if (A.first == Now) {
                        Flag = true;
                        break;
                    }
                }
                if (Flag) {
                    break;
                }
                NowTrie = NowTrie->Fail;
            };
            for (auto A : NowTrie->Child) {
                if (A.first == Now) {
                    NowTrie = A.second;
                    break;
                }
            }
            if (NowTrie->isEnd >= 0) {
                int NowL = Word_Length[NowTrie->isEnd] - 1;
                int FirstY = NowY - (MoveY[7] * NowL);
                int FirstX = NowX - (MoveX[7] * NowL);
                if ((FirstY >= 0) && (FirstY < L) && (FirstX >= 0) && (FirstX < C) && (MAP[FirstY][FirstX] == Word[NowTrie->isEnd][0])) {
                    bool isAbleToPut = false;
                    if (Answer[NowTrie->isEnd].Y != -1) {
                        if (Answer[NowTrie->isEnd].Y > FirstY) {
                            isAbleToPut = true;
                        }
                        else if (Answer[NowTrie->isEnd].Y == FirstY) {
                            if (Answer[NowTrie->isEnd].X > FirstX) {
                                isAbleToPut = true;
                            }
                            else if (Answer[NowTrie->isEnd].X == FirstX) {
                                if (Answer[NowTrie->isEnd].Dir > 'H') {
                                    isAbleToPut = true;
                                }
                            }
                        }
                    }
                    else {
                        isAbleToPut = true;
                    }
                    if (isAbleToPut) {
                        Answer[NowTrie->isEnd].Y = FirstY;
                        Answer[NowTrie->isEnd].X = FirstX;
                        Answer[NowTrie->isEnd].Dir = 'H';
                    }
                }
            }
            NowY += MoveY[7];
            NowX += MoveX[7];
        };
    }
}

void input() {
    cin >> L >> C >> W;
    TRIE* Root = new TRIE();
    Answer.resize(W);
    for (int i = 0; i < W; i++) {
        Answer[i].Y = -1;
    }
    for (int i = 0; i < L; i++) {
        cin >> S;
        for (int j = 0; j < C; j++) {
            MAP[i][j] = S[j];
        }
    }
    for (int i = 0; i < W; i++) {
        cin >> S;
        Word.push_back(S);
        Word_Length[i] = S.length();
        Root->insert_Pattern(S, i);
    };
    Root->find_Fail();
    kmp(Root);
    delete Root;
}

void find_Answer() {
    for (int i = 0; i < Answer.size(); i++) {
        cout << Answer[i].Y << " " << Answer[i].X << " " << Answer[i].Dir << "\n";
    }
}

int main() {
    FASTIO
    input();
    find_Answer();

    return 0;
}

'BOJ > Platinum ~ Diamond' 카테고리의 다른 글

[BOJ/Platinum 3] 백준 13504 XOR 합(C++)  (1) 2023.05.03
[BOJ/Platinum 3] 백준 19585 전설(C++)  (0) 2023.05.03
[BOJ/Platinum 1] 백준 10538 빅 픽쳐(C++)  (0) 2023.05.01
[BOJ/Platinum 1] 백준 2809 아스키 거리(C++)  (1) 2023.05.01
[BOJ/Platinum 5] 백준 9202 Boggle(C++)  (0) 2023.04.05

'BOJ/Platinum ~ Diamond'의 다른글

  • 현재글[BOJ/Diamond 5] 백준 6300 단어 퍼즐(C++)

관련글

댓글

티스토리툴바