uva 10010번 Where's Waldorf?

uva : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=951

 

간단한 dfs 문제

 

* 같은 방향으로 원하는 문자열을 찾으면 되는 문제이다

* 반드시 문자열을 찾을 수 있다.

* 답이 여러개인 경우 가장 왼쪽부근에 위치한 답을 출력하라고 하는데,

  그냥 행->열 순서로 탐색하면 해결된다.

 

alpha 함수는 대소문자가 같은 경우를 리턴하는 함수

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
#include <string>
using namespace std;
 
string arr[51];
bool visit[52][52];
int row, col;
int mx[8] = { 0,1,1,1,0,-1,-1,-1 };
int my[8] = { -1,-1,0,1,1,1,0,-1 };
 
bool alpha(char now_al, char stand) {
    if (now_al == stand || now_al - '0' + 32 == stand - '0' || now_al - '0' - 32 == stand - '0') return true;
    else return false;
}
 
bool dfs(int y, int x, int cnt, string str, int direct) {
    if (cnt == str.size()) return true;
 
    for (int i = 0; i < 8; i++) {
        if (direct == -1 || direct == i) {
            int yy = y + my[i];
            int xx = x + mx[i];
            if (yy >= 0 && yy < row && xx >= 0 && xx < col && !visit[yy][xx]) {
                if (alpha(arr[yy][xx], str[cnt])) {
                    visit[yy][xx] = true;
                    if (dfs(yy, xx, cnt + 1, str, i)) return true;
                    visit[yy][xx] = false;
                }
            }
        }
    }
 
    return false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int testcase;
   cin >> testcase;
 
    while (testcase--) {
       cin >> row >> col;
        for (int i = 0; i < row; i++)
           cin >> arr[i];
        
        vector<pair<int, pair<int, int> > > v;
        int test;
       cin >> test;
        while (test--) {
            string str;
           cin >> str;
            
            bool check = false;
 
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (alpha(str[0], arr[i][j])) {
                        if (dfs(i, j, 1, str, -1)) {
                           cout << i + 1 << " " << j + 1 << "\n";
                            memset(visit, 0, sizeof(visit));
                            check = true;
                            break;
                        }
                    }
                }
                if (check) break;
            }
        }
       cout << "\n";
    }
 
    return 0;
}