1767. [SW Test 샘플문제] 프로세서 연결하기

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
 
int map[12][12];
vector< pair<int,int> > prv;
int mcore;
int mline;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int n;
 
bool chk(int x, int y) {
    if(x<0 || x>n-1 || y<0 || y>n-1)
        return false;
    return true;
}
 
pair<bool, int> draw(int x, int y, int dir, int v) {
    pair<bool, int> res;
    res.first = true; res.second = 0;
 
    if(dir == 4)
        return res;
 
    // check for possibile.
    int nx,ny;
    nx = x + dx[dir]; ny = y + dy[dir];
 
    if(v) {
        while(chk(nx,ny)) {
            //if there's 1 in way, return false.
            if(map[nx][ny]!=0) {
                res.first = false;
                return res;
            }
            nx = nx + dx[dir];
            ny = ny + dy[dir];
        }
    }   
    // then draw with value v
    nx = x + dx[dir]; ny = y + dy[dir];
    while(chk(nx,ny)) {
        map[nx][ny]=v;
        res.second++;
 
        nx = nx + dx[dir];
        ny = ny + dy[dir];
    }
    return res;
}
 
void dfs(int k, int core, int line) {
    if(k >= prv.size())
        return;
    else {
        int x,y;
        x = prv[k].first;
        y = prv[k].second;
 
        pair<bool, int> res;
 
        for(int i=0; i<5; i++) {
            // draw to specific dir.
            res = draw(x,y,i,2);
 
            // draw possible -> place electric line.
            if (res.first) {
                if(i!=4 && mcore < (core+1)) {
                    mcore= core + 1;
                    mline = line + res.second;
                }
                else if(i!=4 && mcore== (core+1)) {
                    if(mline > (line + res.second))
                        mline = line + res.second;
                }
                // do not save status of selection, map itself contains info.
                if (i==4)
                    dfs(k+1, core, line);
                else
                    dfs(k+1, core+1, line + res.second);
 
                // undraw line.
                draw(x,y,i,0);
            }
        }
    }
}
 
int main() {
    int tc;
    scanf("%d", &tc);
    for(int tci=0; tci<tc; tci++) {
        memset(map,0, sizeof(map));
        prv.clear();
        mcore=mline=0;
        scanf("%d", &n);
        int tmp;
 
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                scanf("%d", &tmp);
                map[i][j] = tmp;
                if (tmp == 1 && i!=0 && i != n-1 && j != 0 && j != n-1)
                    prv.push_back(make_pair(i,j));
            }
        }
        dfs(0, 0, 0);
        printf("#%d %d\n", tci+1, mline);
    }
}