1949. [모의 SW 역량테스트] 등산로 조성

문제: https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

 

 

 

 소스코드:

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
#include <deque>

using namespace std;

int tc, n,mi, dist[51][51], arr[51][51],res;
typedef pair<int, int> P;

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
vector<P> adj;
queue<P> q;

int dfs(int curx,int cury) {
	if (dist[curx][cury]) return dist[curx][cury];
	dist[curx][cury] = 1;
	for (int i = 0; i < 4; i++) {
		int x = curx + dx[i];
		int y = cury + dy[i];
		if (x < 0 || x >= n || y < 0 || y >= n || arr[curx][cury] <= arr[x][y]) continue;

		dist[curx][cury]=max(dist[curx][cury],dfs(x, y)+1);
	}
	return dist[curx][cury];
}
void func() {
	
	for (int z = 0; z < adj.size(); z++) {
		memset(dist, 0, sizeof(dist));
		res = max(res, dfs(adj[z].first, adj[z].second));
	}
	for (int k = 1; k <= mi; k++) {

		memset(dist, 0, sizeof(dist));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				arr[i][j] -= k;
				for (int z = 0; z < adj.size(); z++) {
					memset(dist, 0, sizeof(dist));
					res=max(res,dfs(adj[z].first, adj[z].second));
				}
				arr[i][j] += k;
			}
		}
	}

}

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

	
	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		cin >> n>>mi;
		res = 1; 
		adj.clear();
		int tmp = 0;
		
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				cin >> arr[j][k];
				if (tmp < arr[j][k]) {
					tmp = arr[j][k];
				}
			}
		}
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (arr[j][k]==tmp) {
					adj.push_back({ j,k });
				}
			}
		}
		func();
		cout <<"#"<<i<<" "<< res << '\n';
	}
	return 0;
}