반응형
https://www.acmicpc.net/problem/6983
6983번: Where's Waldorf?
The input begins with a number on a line by itself, indicating the number of test cases that follow. Each test case consists of a pair of integers, m followed by n, 1 ≤ m ≤ 50 and 1 ≤ n ≤ 50 in decimal notation on a single line. The next m lines co
www.acmicpc.net
문제풀이
>문자열을 입력받아 미리 입력된 문자판에서 찾기(낱말찾기와 유사)
>문자판에서 해당되는 문자를 검색하고 찾은 후에는 전체 문자열의 모든 문자를 찾는 방식
(복잡도는 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;
}반응형