#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int m_s;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, m;
vector<pair<int, int>> path_copy;
void dfs(vector<vector<int>>& arr, vector<vector<bool>>& visited, int y, int x, int d, int s, vector<pair<int, int>> path) {
if (visited[y][x]) {
return ;
}
visited[y][x] = true;
path.push_back({y, x});
if (d >= 3) {
visited[y][x] = false;
// m_s 갱신
if (m_s < s) {
m_s = s;
path_copy = path;
}
return ;
}
for (int i = 0; i < 4; i++) {
int next_y = y + dir[i][0];
int next_x = x + dir[i][1];
if (0 <= next_y && next_y < n && 0 <= next_x && next_x < n && !visited[next_y][next_x]) {
dfs(arr, visited, next_y, next_x, d + 1, s + arr[next_y][next_x], path);
}
}
visited[y][x] = false;
}
int main(int argc, char** argv)
{
cin >> n >> m;
vector<vector<int>> arr(n, vector<int>(n));
vector<vector<bool>> visited(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
vector<pair<int, int>> lo(m);
for (int i = 0; i < m; i++) {
int y, x;
cin >> y >> x;
lo[i] = {y - 1, x - 1};
visited[y - 1][x - 1] = true;
}
vector<int> p(m);
for (int i = 0; i < m; i++) {
p[i] = i;
}
int result = 0;
vector<vector<bool>> initial_visited = visited;
do {
int all_s = 0;
for (int j = 0; j < m; j++) {
auto l = lo[p[j]];
int y = l.first;
int x = l.second;
visited[y][x] = false;
vector<pair<int, int>> path;
m_s = 0;
dfs(arr, visited, y, x, 0, arr[y][x], path);
for (auto& p : path_copy) {
visited[p.first][p.second] = true;
}
path_copy.clear();
all_s += m_s;
}
visited = initial_visited;
result = max(all_s, result);
} while (next_permutation(p.begin(), p.end()));
cout << result << endl;
return 0;
}
경로를 알아야하기때문에 dfs 사용
중요한 부분은 각 친구들의 위치 정보에 대한 순열이 필요한 것인데,
모든 순열에 대해서 최대 수확량을 계산해줘야함
그렇지 않으면, 예를 들어 1번 친구가 2번 친구의 최대 수확량 경로를 침범해서 최대 수확량이 안될수가 있기때문