반응형
18290번: NM과 K (1)
크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접
www.acmicpc.net
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <iostream> #include <algorithm> #include <vector> using namespace std; int n, m, k, arr[11][11]; int visited[11][11]; // 모든 숫자가 음수일 수도 있으므로 -987654321으로 초기화 int ans = -987654321, temp = 0; vector<pair<int, int> > v; void visit(int i, int j, int state) { if (state == 1) { // 겹치는 영역이 두 개 이상일 수도 있으므로 visited[][]=1이 아닌 visited[][]++ visited[i][j]++; if (i - 1 >= 0) visited[i - 1][j]++; if (j - 1 >= 0) visited[i][j - 1]++; if (i + 1 < n) visited[i + 1][j]++; if (j + 1 < m) visited[i][j + 1]++; } else { visited[i][j]--; if (i - 1 >= 0) visited[i - 1][j]--; if (j - 1 >= 0) visited[i][j - 1]--; if (i + 1 < n) visited[i + 1][j]--; if (j + 1 < m) visited[i][j + 1]--; } } void dfs(int x, int y, int cnt) { if (cnt == k) { ans = max(ans, temp); return; } for (int i = x; i < n;i++) { y = 0; for (int j = y; j < m;j++) { if (visited[i][j]==0) { visit(i, j, 1); temp += arr[i][j]; v.push_back({ i,j }); dfs(i, j, cnt + 1); v.erase(v.end() - 1); temp -= arr[i][j]; visit(i, j, 0); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) cin >> arr[i][j]; } dfs(0, 0, 0); cout << ans; } | cs |
반응형