[21772] 가희의 고구마 먹방

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

21772번: 가희의 고구마 먹방

<문제>

중복 방문 허용/같은 위치의 고구마를 중복으로 세는 경우를 주의해야한다.

입력이 작으므로 5방향으로 구현해도 무리가 없다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, t, sy, sx, ans = -1, dy[5] = {0, 1, 0, -1, 0},
                     dx[5] = {1, 0, -1, 0, 0};
char a[103][103];
bool visited[101][101];
void f(int y, int x, int turn, int cnt) {
    if (turn == t) {
        ans = max(cnt, ans);
        return;
    }
    int i;
    for (i = 0; i < 5; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        if (a[ny][nx] == '#') continue;
        if (a[ny][nx] == 'S') {
            a[ny][nx] = '.';
            f(ny, nx, turn + 1, cnt + 1);
            a[ny][nx] = 'S';
        } else
            f(ny, nx, turn + 1, cnt);
    }
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> t;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'G') {
                sy = i;
                sx = j;
            }
        }
    f(sy, sx, 0, 0);
    cout << ans;
    return 0;
}