[백준] 16988 Baaaaaaaaaduk2 (Easy)

 

문제가 참 길다 이해하기가 풀기보다 더 어려운 문제다

요약하자면 내가 돌을 2개 둘 때 상대 돌을 최대 몇개 잡아먹을 수 있냐다

상대 돌을 잡아먹는다는건 상대돌주변에 1 or 범위밖으로 구성되면된다 빈틈없이!

 

2개만 두기때문에 쉬운문제로 변해버린다

그냥 2중 for문으로 두곳정하면된다!

 

이 때 배열을 1차원으로 보자 편하게 최대 n*m으로

배열을 둔 다음에는 더 쉽다 그냥 dfs 돌려보면 된다!

끝!

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int INF = 400;
int n,m,ans,s;
int map[22][22];
bool check[22][22];
 
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
 
vector<pair<int,int>> vt;
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<m);
}
 
int dfs(int x,int y){
    if(check[x][y] || !inner(x,y) || map[x][y]==1) return 0;
    if(map[x][y]==0) return INF;
    check[x][y]=true;
    int ret=1;
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        ret+=dfs(nx,ny);
    }
    return ret;
}
 
void solve(){
    memset(check,0,sizeof(check));
    int ret=0;
    for(int i=0;i<s;i++){
        int x = vt[i].first, y=vt[i].second;
        if(!check[x][y]) {
            int cnt = dfs(x,y);
            if(cnt<INF) ret+=cnt;
        }
    }
    if(ret<INF) ans = max(ans,ret);
}
 
int main(){
    scanf(" %d %d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf(" %d",&map[i][j]);
            if(map[i][j]==2) vt.push_back({i,j});
        }
    }
    s = vt.size();
    for(int i=0;i<n*m;i++){
        for(int j=i+1;j<n*m;j++){
            int x1 = i/m, y1=i%m;
            int x2 = j/m, y2=j%m;
            if(!map[x1][y1] && !map[x2][y2]){
                map[x1][y1]=map[x2][y2]=1;
                solve();
                map[x1][y1]=map[x2][y2]=0;
            }
        }
    }
    printf("%d\n",ans);
}