17406 배열 돌리기 4

https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

 

백트래킹으로 가능한 경우의 수를 모두 만들고, 한 번 씩 해본 다음에 ans를 갱신하면 될 것 같다. 

회전하는 부분만 잘 구현하면 할 만 할 것 같다. 지금 이동중인 ny nx가 이동경로 내에 있다는 것을 확인하는 if문 조건에서 start와 n 부분 조건을 빼서 문제를 찾는데 시간이 걸렸다. 어제 한 번 실패하고 내 방식대로 구현해봤는데 바로 성공해서 놀랐다.

 

#include <bits/stdc++.h>

using namespace std;

#define Y first

#define X second

int n,m,k; //세로 가로 회전수

int board[53][53];

int duplicated[53][53]; //보드 복사할 곳

int r[10],c[10],s[10];

int ans=0x7f777777;

int arr[10];

bool isused[10];

int findMin(){

    int ret=0x7f777777;

    for(int i=0;i<n;i++){

        int val=0;

        for(int j=0;j<m;j++) val+=duplicated[i][j];

        ret=min(ret,val);

    } return ret;

}

void rotBoard(int idx){

    int dy[4]={0,1,0,-1};

    int dx[4]={1,0,-1,0};

    int sy=r[idx]-s[idx]; int sx=c[idx]-s[idx];

    int ey=r[idx]+s[idx]; int ex=c[idx]+s[idx];

    int cnt=s[idx];

    for(int i=0;i<cnt;i++){ //cnt만큼 안으로 들어감

        int dir=0;

        int y=sy; int x=sx;

        int memoVal=duplicated[y][x];

        while(dir<4){

            int ny=y+dy[dir];

            int nx=x+dx[dir];

            if(ny==sy && nx==sx){ //처음 좌표에 도달했다면

                duplicated[ny][nx]=memoVal;

                break;

            }

            //ny가 범위 내에 있다 -> sy<=ny&&ny<=ey-i

            if((sy<=ny&&ny<=ey-i)&&(sx<=nx&&nx<=ex-i)){ //정사각형 안에 있다면

                int tmp = duplicated[ny][nx];

                duplicated[ny][nx]=memoVal;

                memoVal=tmp;

                y=ny; x=nx; //좌표 이동

            }

            else dir++;

        }

        sy++; sx++; //한 번 안으로 들어감

    }

}

void func(int cnt){

    if(cnt==k){

        //보드 복사

        for(int i=0;i<n;i++)

            for(int j=0;j<m;j++)

                duplicated[i][j]=board[i][j];

        //보드 회전

        for(int i=0;i<k;i++) rotBoard(arr[i]);

        //ans 갱신

        ans=min(ans,findMin());

        return;

    }

    for(int i=0;i<k;i++){

        if(isused[i]) continue;

        isused[i]=true;

        arr[cnt]=i;

        func(cnt+1);

        isused[i]=false;

    }

}

int main(){

    ios::sync_with_stdio(0); cin.tie(0);

    cin>>n>>m>>k;

    for(int i=0;i<n;i++)

        for(int j=0;j<m;j++)

            cin>>board[i][j];

    for(int i=0;i<k;i++){cin>>r[i]>>c[i]>>s[i]; r[i]--; c[i]--;}

    func(0);

    cout<<ans;

    return 0;

}