SWEA 1949 등산로 조성

코드:

/* 1. visited 값을 v로 설정했으면 not visited는 !vst[nr][nc]가 아니라 vst[nr][nc] != v */
/* 2. 깎는 건 한 번만 */
/* 3. 전역 변수 초기화 */
/* 4. 깎는 횟수만큼 재방문 가능해야 하므로 재방문 허용 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T;
int N, K;
int map[8][8];
bool vst[8][8];
int ans;

const int dr[] = { -1, 0, 1, 0 };
const int dc[] = { 0, 1, 0, -1 };
#define IN(r, c) (0 <= (r) && (r) < N && 0 <= (c) && (c) < N)

void DFS(int r, int c, int l, bool b) {
	vst[r][c] = 1;

	bool stm = true;
	for (int d = 0; d < 4; ++d) {
		int nr = r + dr[d], nc = c + dc[d];
		if (IN(nr, nc) && !vst[nr][nc]) {	/* 1 */
			if (map[nr][nc] < map[r][c]) {
				stm = false;
				DFS(nr, nc, l + 1, b);
			}
			if (b) {
				stm = false;
				int org = map[nr][nc];
				for (map[nr][nc] = org - K; map[nr][nc] < min(map[r][c], org); ++map[nr][nc]) {
					DFS(nr, nc, l + 1, 0);
				}
				map[nr][nc] = org;
			}
		}
	}
	if (stm && l > ans) {
		ans = l;
	}
	vst[r][c] = 0;	/* 4 */
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> T;
	for (int t = 1; t <= T; ++t) {
		cin >> N >> K;

		int pkh = 0; vector<pair<int, int>> pk;
		for (int r = 0; r < N; ++r) {
			for (int c = 0; c < N; ++c) {
				cin >> map[r][c];
				if (map[r][c] >= pkh) {
					if (map[r][c] != pkh) {
						pkh = map[r][c];
						pk.clear();
					}
					pk.emplace_back(r, c);
				}
			}
		}

		ans = 0;	/* 3 */
		for (auto p : pk) {
			DFS(p.first, p.second, 1, 1);
		}

		cout << '#' << t << ' ' << ans << '\n';
	}
	return 0;
}