[Programming Challenges] 월리를 찾아라 - 난이도(하중)

[ 문제 ]

글자들로 이루어진 m * n 그리드와 단어 목록이 주어졌을 때 그리드에서 단어를 찾을 수 있는 위치를 구하라. 그리드에서 한 줄로 연결된 글자들만 단어에 매치될 수 있다. 대소문자는 구분하지 않는다. 또한 단어를 매치시킬 때 수평, 수직, 대각선으로 총 여덟 개의 방향으로 매치시킬 수 있다.

 

[ 입 출력 조건 ]

입력 첫 번째 줄에는 케이스의 개수이다. 각 케이스는 한 쌍의 정수 m과 n이 들어있는 행으로 시작되며 이때 m, n은 1 이상 50이하의 10진수 정수다. 그 다음 m개의 행에는 각각 n개씩의 글자가 들어있으며 이 그리드에서 단어를 찾아야 한다. 그리드에 있는 글자는 대문자일 수도 있고 소문자일 수도 있다. 글자들로 이루어진 그리드 다음 줄에는 k라는 정수가 입력된다(1<=K<=20). 그 아래에는 k줄에 걸쳐서 검색할 단어가 한 줄에 하나씩 입력된다. 단어를 입력할 때는 대문자와 소문자밖에 쓸 수 없다. 즉 스페이스나 하이픈과 같이 알파벳을 제외한 문자는 전혀 사용할 수 없다.   출력  각 테스트 케이스마다 각 단어에 대해 그리드에서 그 단어가 있는 위치를 나타내는 한 쌍의 정수를 출력한다. 두 정수 사이에는 스페이스가 한 개 들어간다. 첫 번째 정수는 주어진 단어의 첫 번째 글자를 찾을 수 있는 행(맨 윗줄은 1, 맨 아랫줄은 m)을 나타내고 두 번째 정수는 주어진 단어의 첫 번째 글자를 찾을 수 있는 단어의 위치를 출력한다(즉 단어의 첫 번째 글자가 가장 위에 있는 단어의 위치를 출력한다). 같은 줄에 같은 단어가 두 번 이상 나오면 그 중에서 가장 왼쪽에 있는 단어의 위치를 출력한다. 모든 단어는 그리드에서 한 번 이상 등장한다. 두 개의 서로 다른 케이스에 대한 출력 결과 사이엔 빈 줄을 하나 출력한다.

[ 입출력 예 ]

1 6 8 dbFdxHYo IaVNewTd aDvEntuR YoYoYoYo McIeNOto BiDorKWa 6 yo cieno dia adventur yoyo dork

1 7 5 2 1 1 3 1 4 1 6 3

Self-reflection

인덱스 계산하다가  망함. 이런 문제는 함수화를 잘 시켜서 푸는 것이 디버깅을 용이하게 한다.

Code

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

#include<stdio.h> #include<string.h>   int gx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int gy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };   char Map[300][300] = { 0, }; char cinput[1000]; int nStrlen = 0; int m, n; bool isMode = false;   void FindWaldorf(int x, int y, int index, int position) {     if (Map[x][y] != cinput[index])         return;       if (index >= nStrlen - 1)     {         isMode = true;         return;     }       FindWaldorf(x + gx[position], y + gy[position], index + 1, position); }   void Run() {     for (int i = 0; i < m; i++)     {         for (int j = 0; j < n; j++)         {             for (int k = 0; k < 8; k++)             {                 FindWaldorf(i, j, 0, k);                   if (isMode)                 {                     printf("%d %d\n", i + 1, j + 1);                     isMode = false;                     return;                 }              }          }     } }   //대소문자 바꾸는 함수  void Strupr(char* str) {     int len = strlen(str);       for (int i = 0; i < len; i++)     {         if (str[i] >= 'A' && str[i] <= 'Z')             str[i] = str[i] + 32;     } }     int main() {     int nCount = 0;       scanf( "%d", &nCount);     for (int h = 0; h < nCount; h++)     {         scanf("%d %d", &m, &n);           for (int i = 0; i < m; i++)         {             char str[1000] = { 0, };               scanf("%s", str);             Strupr(str);               strcpy(Map[i], str);         }           int input = 0;           scanf("%d", &input);           for (int k = 0; k < input; k++)         {             scanf( "%s", cinput);               nStrlen = strlen(cinput);             Strupr(cinput);             Run();         }         printf("\n");             }     return 0; }