Where's Waldorf?

https://www.acmicpc.net/problem/6983

6983번: Where's Waldorf?

문제풀이

>문자열을 입력받아 미리 입력된 문자판에서 찾기(낱말찾기와 유사)

>문자판에서 해당되는 문자를 검색하고 찾은 후에는 전체 문자열의 모든 문자를 찾는 방식

(복잡도는 n^2이지만 가지치기로 최대한 시간을 줄이는게 목표)

 

배울점

>효율적인 알고리즘은 찾지 못했지만 가지치기로 최대한 경우의 수를 줄여보았다.

 

소스>성공

 

#include <stdio.h>
#include <string.h>
int len;
char map[50][50];
char string[50];

int check(int s, int t, int x, int y)
{
    int l = 1;
    while (len > l)
    {
        x += s;
        y += t;
        if (x > 50 || x < 0 || y > 50 || y < 0)
            return 0;
        if (map[x][y] == string[l++])
            ;
        else
            return 0;
    }
    return 1;
}
char change(char c)
{
    if (c <= 90)
        return c + 32;
    else
        return c;
}

int main()
{
    int Case, m, n, k;
    char line[256];
    int x, y, sucess;
    int i, j;
    int t;
    scanf("%d", &Case);
    t = 0;
    while (Case--)
    {
        if (t)
            printf("\n");
        t = 1;
        gets(line);
        scanf("%d %d", &m, &n);
        for (i = 0; i < m; i++)
            scanf("%s", &map[i]);
        for (i = 0; i < m; i++)
            for (j = 0; j < n; j++)
                map[i][j] = change(map[i][j]);
        scanf("%d", &k);
        while (k--)
        {
            scanf("%s", &string);
            len = strlen(string);
            for (i = 0; i < len; i++)
                string[i] = change(string[i]);
            for (i = 0; i < m; i++)
            {
                sucess = 0;
                for (j = 0; j < n; j++)
                {
                    if (map[i][j] == string[0])
                    {
                        x = i;
                        y = j;
                        if (x >= len)
                            if (check(-1, 0, x, y))
                            {
                                sucess = 1;
                                break;
                            }
                        if (check(-1, 1, x, y))
                        {
                            sucess = 1;
                            break;
                        }
                        if (n - y >= len)
                            if (check(0, 1, x, y))
                            {
                                sucess = 1;
                                break;
                            }
                        if (check(1, 1, x, y))
                        {
                            sucess = 1;
                            break;
                        }
                        if (m - x >= len)
                            if (check(1, 0, x, y))
                            {
                                sucess = 1;
                                break;
                            }
                        if (check(1, -1, x, y))
                        {
                            sucess = 1;
                            break;
                        }
                        if (y >= len)
                            if (check(0, -1, x, y))
                            {
                                sucess = 1;
                                break;
                            }
                        if (check(-1, -1, x, y))
                        {
                            sucess = 1;
                            break;
                        }
                    }
                }
                if (sucess)
                {
                    printf("%d %d\n", x + 1, y + 1);
                    break;
                }
            }
        }
    }
    return 0;
}