글 읽기 - 반례를 모르겠습니다 ㅠㅠ

ckhee93 6년 전 0

dfs로 모든 경우의수를 찾으면서 5번 움직여보는 경우의 수가 찾아지면 calc함수를 호출해서 직접 움직여보며 가장 큰 수를 출력합니다.

계산할 때 마다 map변수에 input변수를 복사해서 계산하므로 이전 데이터가 남아있진 않구요..

움직이는 함수들도 몇번 테스트 해봐도 잘 돌아가는것같은데 시작하자마다 틀렸다고 나오네요 ㅠㅠ

질문에 있는 테스트 케이스들도 전부 돌려봤습니다.

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int map[21][21];
int input[21][21];

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int moving[5];
int ans = -1;
void printM(){
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            cout<<map[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
void moveU(){
    int dir = 0;
    int check[21][21]={};
    for(int j = 0;j<N;j++){
        for(int i = 1;i<N;i++){
            int nx = i;
            int ny = j;
            while(map[i][j]){
                nx += dx[dir];
                ny += dy[dir];
                //맵 범위 벗어나면 맵 끝에 위치
                if(nx <0 || ny < 0 || nx >=N || ny >=N){
                    nx -= dx[dir];
                    ny -= dy[dir];
                    map[nx][ny] = map[i][j];
                    map[i][j] = 0;
                }
                //검사중 같은 숫자가 있으면 합침
                if(!check[nx][ny] && map[nx][ny] == map[i][j]){
                    map[nx][ny] *= 2;
                    map[i][j] = 0;
                    check[nx][ny] = 1;
                    
                }else if(map[nx][ny]){
                    //이미 합쳐진 셀이거나 같은 숫자가 아니면 좌표 되돌림
                    nx -= dx[dir];
                    ny -= dy[dir];
                    //되돌려진 위치가 현재 위치랑 같으면 break
                    if(nx == i && ny == j) break;
                    map[nx][ny] = map[i][j];
                    map[i][j] = 0;
                    
                }
            }
        }
    }
}
void moveD(){
    int dir = 1;
    int check[21][21]={};
    for(int j = 0;j<N;j++){
        for(int i = N-2;i>=0;i--){
            int nx = i;
            int ny = j;
            while(map[i][j]){
                nx += dx[dir];
                ny += dy[dir];
                if(nx <0 || ny < 0 || nx >=N || ny >=N){
                    nx -= dx[dir];
                    ny -= dy[dir];
                    map[nx][ny] = map[i][j];
                    map[i][j] = 0;
                }
                if(!check[nx][ny] && map[nx][ny] == map[i][j]){
                    map[nx][ny] *= 2;
                    map[i][j] = 0;
                    check[nx][ny] = 1;
                    
                }else if(map[nx][ny]){
                    nx -= dx[dir];
                    ny -= dy[dir];
                    if(nx == i && ny == j) break;
                    map[nx][ny] = map[i][j];
                    map[i][j] = 0;
                    
                }
            }
        }
    }
}
void moveL(){
    int dir = 2;
    int check[21][21]={};
    for(int i = 0;i<N;i++){
        for(int j = 1;j<N;j++){
            int nx = i;
            int ny = j;
            while(map[i][j]){
                nx += dx[dir];
                ny += dy[dir];
                if(nx <0 || ny < 0 || nx >=N || ny >=N){
                    nx -= dx[dir];
                    ny -= dy[dir];
                    map[nx][ny] = map[i][j];
                    map[i][j] = 0;
                }
                if(!check[nx][ny] && map[nx][ny] == map[i][j]){
                    map[nx][ny] *= 2;
                    map[i][j] = 0;
                    check[nx][ny] = 1;
                }else if(map[nx][ny]){
                    nx -= dx[dir];
                    ny -= dy[dir];
                    if(nx == i && ny == j) break;
                    map[nx][ny] = map[i][j];
                    map[i][j] = 0;
                }
            }
            
        }
    }
}
void moveR(){
    int dir = 3;
    int check[21][21]={};
    for(int i = 0;i<N;i++){
        for(int j = N-2;j>=0;j--){
            int nx = i;
            int ny = j;
            while(map[i][j]){
                nx += dx[dir];
                ny += dy[dir];
                if(nx <0 || ny < 0 || nx >=N || ny >=N){
                    nx -= dx[dir];
                    ny -= dy[dir];
                    map[nx][ny] = map[i][j];
                    map[i][j] = 0;
                }
                if(!check[nx][ny] && map[nx][ny] == map[i][j]){
                    map[nx][ny] *= 2;
                    map[i][j] = 0;
                    check[nx][ny] = 1;
                    
                }else if(map[nx][ny]){
                    nx -= dx[dir];
                    ny -= dy[dir];
                    if(nx == i && ny == j) break;
                    map[nx][ny] = map[i][j];
                    map[i][j] = 0;
                }
            }
        }
    }
}

int calc(){
    //맵 복사
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            map[i][j] = input[i][j];
        }
    }
    
    for(int i = 0;i<5;i++){
        switch(moving[i]){
            case 0: moveU();break;
            case 1: moveD();break;
            case 2: moveL();break;
            case 3: moveR();break;
        }
    }
    int mx = -1;
    
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            mx = max(mx,map[i][j]);
        }
    }
    return mx;
}
void dfs(int depth){
    if(depth == 5){
        int res = calc();
        if(ans < res){
            ans = res;
        }
    }else{
        for(int i = 0;i<4;i++){
            moving[depth] = i;
            dfs(depth+1);
        }
    }
}
int main(){
    freopen("input.txt","r",stdin);
    cin >> N;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            cin >> input[i][j];
            map[i][j] = input[i][j];
        }
    }
    dfs(0);
   
    cout<<ans<<endl;
}