Lv. 3 함께하는 효도 - C++

#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번 친구의 최대 수확량 경로를 침범해서 최대 수확량이 안될수가 있기때문