p10010 ( Where's Waldorf )

문제

 

문자들이 적혀있는 표( 배열, 격자 ) 에서 왼쪽 위에서부터 오른쪽 밑으로 탐색하여 찾고자 하는 문자열을 8방향으로 탐색, 탐색에 성공하면 현재 위치를 출력하는 문제이다.

 

 

추가조건으로 문자의 대소문자를 구분하지 않는다.

 

 

위의 예제에 대하여 나타내면 다음과 같다.

 

 

입력되는 격자의 최대 크기가 50 x 50이고, 찾는 문자열의 길이는 최대 20이다.

격자의 각 위치마다 8방향을 탐색하고, 최대 길이가 20이므로 단순하게 50 x 50 x 8 x 20으로 계산을 해보더라도 40만이다. 

 

그냥 좌측 위를 ( 0, 0 )으로 두고 오른쪽 아래로 나아가며 8방향 탐색을 하면 된다고 판단했다.

 

 

 

소스코드.

#include<iostream>
#include<vector>
using namespace std;
#pragma warning(disable:4996);

int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
int dy[8] = { 0,-1,-1,-1,0,1,1,1 };
char grid[50][50];
int n, m;

bool solve(string str, int x, int y) {
	for (int i = 0; i < 8; i++) {
		int count = 0;
		int nx = x, ny = y;
		while (count < str.length()) {
			if (grid[nx][ny] != str[count]) break;
			if (nx < 0 || n <= nx || ny < 0 || m <= ny) break;

			nx = nx + dx[i];
			ny = ny + dy[i];
			count++;
			
			if (count == str.length()) {
				cout << x + 1 << " " << y + 1 << '\n';
				return true;
			}

		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int repeat;
	string str;
	vector<string> strings;

	cin >> repeat;
	while (repeat--) {
		cin >> n >> m;
		
		for (int i = 0; i < n; i++) {
			cin >> grid[i];
			for (int j = 0; j < m; j++) {
				if (grid[i][j] < 97)
					grid[i][j] += 32;
			}
		}

		int k;
		cin >> k;
		while (k--) {
			cin >> str;
			for (int i = 0; i < str.length(); i++) {
				if (str[i] < 97)
					str[i] += 32;
			}

			bool flag = false;
			for (int i = 0; i < n && !flag; i++) {
				for (int j = 0; j < m && !flag; j++) {
					if (str[0] == grid[i][j]) {
						if (solve(str, i, j))
							flag = true;
					}
				}
			}
		}
		if(repeat > 0)
			cout << "\n";
	}
	
	return 0;
}