소프티어

일단 깊이 재는 데 편하려고 DFS 썼고, 3 초과일때 탐색 빠꾸 먹여서 해봤는데...기본 예제 입력(테케1)만 맞고 다 틀리네요..어떤 부분에서 발상이 잘못된지 알려주세요..

소스는 다음과 같습니다..

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


using namespace std;
typedef pair<int,int> iter2dim;


iter2dim i2dim[4] = {
    make_pair(-1,0),
    make_pair( 1,0),
    make_pair(0,-1),
    make_pair(0, 1)
};
int N;


bool avail(int x, int y) {
    if(x<0 or y<0) return false;
    if(x>=N or y>=N) return false;
    return true;
}


void dfs(int ** &farm, int x, int y, int count, int &sum) {
    if(!avail(x,y)) return;
    if(farm[x][y] == 0) return;
    if(count >= 4) return;
    sum += farm[x][y];
    farm[x][y] = 0;
    int maxVal = 0, recurX = x, recurY = y;
    for(int i = 0; i < 4; i++) {
        int tmpX = x+i2dim[i].first, tmpY = y+i2dim[i].second;
        if(avail(tmpX,tmpY) && farm[tmpX][tmpY] > 0) {
            if(maxVal<farm[tmpX][tmpY]) {
                maxVal = farm[tmpX][tmpY];
                recurX = tmpX;
                recurY = tmpY;
            }
        }
    }
    if(recurX != x or recurY != y) dfs(farm,recurX,recurY,count+1,sum);
}




int main(int argc, char** argv)
{
    int M;
    cin >> N >> M;
    int **farm = new int *[N];
    for(int i = 0; i < N; i++) {
        farm[i] = new int[N];
        for(int j = 0; j < N; j++) {
            cin >> farm[i][j];
        }
    }
    vector<pair<int,int>> v;
    for(int i = 0 ; i < M; i++ ) {
        int X, Y;
        cin >> X >> Y;
        v.push_back(make_pair(X,Y));
    }
    int sum = 0, tmp = 0, answer = 0;
    do {
        for(auto itm:v) {
            tmp = 0;
            dfs(farm,itm.first-1,itm.second-1,0,tmp);
            sum += tmp;
        }
        if(sum>answer) answer = sum;
    } while(next_permutation(v.begin(),v.end()));
    cout << answer;
   return 0;
}

+이것도 틀렸네요,,,

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
constexpr int CNT = 3;
typedef pair<int,int> iter2dim;
vector<vector<int>> farm;
vector<vector<bool>> visited;
typedef pair<int,iter2dim> pth;
set<pth> path_visited;
iter2dim i2dim[4] = {
    make_pair(-1,0),
    make_pair( 1,0),
    make_pair(0,-1),
    make_pair(0, 1)
};
int N;
bool avail(int x, int y) {
    if(x<0 or y<0) return false;
    if(x>=N or y>=N) return false;
    return true;
}
void dfs(int x, int y, int count, int &sum) {
    if(!avail(x,y)) return;
    if(visited[x][y]) return;
    if(count > CNT) return;
    sum += farm[x][y];
    visited[x][y] = true;
    int maxVal = 0, recurX = x, recurY = y;
    for(int i = 0; i < 4; i++) {
        int tmpX = x+i2dim[i].first, tmpY = y+i2dim[i].second;
        if(avail(tmpX,tmpY) and !visited[tmpX][tmpY]) {
            if(maxVal<=farm[tmpX][tmpY]) {
                maxVal = farm[tmpX][tmpY];
                recurX = tmpX;
                recurY = tmpY;
            }
        }
    }
    pth p = make_pair(count,make_pair(recurX,recurY));
    if(path_visited.find(p) != path_visited.end()) {
        return;
    }
    path_visited.insert(p);
    if(count < CNT) dfs(recurX,recurY,count+1,sum);
    path_visited.erase(p);
}
int main(int argc, char** argv)
{
    int M;
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        farm.push_back(vector<int>());
        visited.push_back(vector<bool>());
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            int n;
            cin >> n;
            farm[i].push_back(n);
            visited[i].push_back(false);
        }
    }
    int sum = 0;
    vector<iter2dim> v;
    for(int i = 0; i < M; i++) {
        iter2dim iter;
        cin >> iter.first >> iter.second;
        iter.first--;
        iter.second--;
        v.push_back(iter);
    }
    do {
        int tmp = 0;
        for(auto i : v) {
            path_visited.insert(make_pair(0,make_pair(i.first,i.second)));
            dfs(i.first,i.second,0,tmp);
        }
        for(auto i : visited) {
            fill(i.begin(),i.end(),0);
        }
        if(tmp > sum) sum = tmp;
    } while(next_permutation(v.begin(),v.end()));
    cout << sum;
   return 0;
}