백준 1103 게임 혼내주기

 

처음에 bfs로 방문한 곳을 다시 방문할 수 있으면 -1을 출력하도록 구현했는데 틀렸다. 아무리 생각해도 틀릴 이유가 없는데 틀려서 질문글에서 반례를 찾고 dfs + dp로 바꿔서 풀었다. 반례는 스포 방지를 위해 맨 아래에 적어두었다.

 

이 문제 또한 실제 코딩테스트 문제였으면 반례를 떠올리지 못했을 것 같다... 경우의 수를 좀 더 엄밀하게 생각하는 능력을 기르고 싶다...

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool visited[50][50];
int board[50][50], cache[50][50];
int n, m;

void input() {
    fastio;
    cin >> n >> m;
    string s;
    for(int i = 0; i < n; ++i){
        cin >> s;
        for(int j = 0; j < m; ++j) {
            if(s[j] == 'H') board[i][j] = -1;
            else board[i][j] = s[j] - '0';
        }
    }
}

int d(int x, int y) {
    int& ret = cache[x][y];
    if(ret != -1) return ret;

    ret = 0;
    for(int i = 0; i < 4; ++i) {
        int offset = board[x][y];
        int nx = x + dx[i]*offset, ny = y + dy[i]*offset;
        if(nx < 0 || nx >= n || ny < 0 || ny >= m || board[nx][ny] == -1) continue;
        if(visited[nx][ny]) {
            cout << -1;
            exit(0);
        }
        visited[nx][ny] = true;
        ret = max(ret, d(nx, ny)+1);
        visited[nx][ny] = false;
    }
    return ret;
}

int main() {
    input();
    memset(cache, -1, sizeof(cache));
    visited[0][0] = true;
    cout << d(0, 0)+1;
}

 

4 4
3HH2
H1HH
H2H1
2219

 

답: 8