아직 계정이 없으신가요? 회원가입

Dev. Talk

Garage Game 반례를 찾고싶습니다 고수님들 도와주세요

회원사진girlzzz03
351 views2021-10-20 01:17

아래 코드로 fail 7개 뜨네요 ㅠㅠ 고수님들의 도움 기다립니다,,



#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
#include<string.h>

using namespace std;

int N;
int new_block[45][15] = {0, };
int visit[45][15] = {0, };
int answer = 0;
int real_answer = 0;
stack<int> answer_stack;

bool compare(pair <int,int> p1, pair <int,int> p2){
    if (p1.second == p2.second) {
        return p1.first < p2.first;
    }    
    return p1.second < p2.second;
}

int dfs(int x, int y, int ref_val, vector<pair<int, int> > &block_vectors)
{
    if(x<2*N || x>=3*N || y<=-1 || y>=N) return false;
    
    if((!visit[x][y]) && (new_block[x][y] == ref_val))
    {
        visit[x][y] = true;
        block_vectors.push_back({x, y});
        dfs(x-1, y, ref_val, block_vectors);
        dfs(x+1, y, ref_val, block_vectors);
        dfs(x, y-1, ref_val, block_vectors);
        dfs(x, y+1, ref_val, block_vectors);

        return true;
    }
    return false;
}

int score = 0;
int get_blocks(int ref_val, vector<pair<int, int> > &block_vectors)
{
    int elem_cnt = 0;
    int rect_size = 0;
    int block_answer = 0;
    int max_x = 0;
    int max_y = 0;
    int min_x = 0;
    int min_y = 0;
    int block_size = 0;
    

    for(int i=2*N; i<3*N; i++){
        for(int j=0; j<N; j++){
        	vector<pair<int, int> > find_block_vectors;
            dfs(i, j, ref_val, find_block_vectors);
            if(block_size < find_block_vectors.size()){
                block_vectors = find_block_vectors;
                block_size = find_block_vectors.size();
            }
        }
    }
   

    elem_cnt = block_vectors.size();

    if(elem_cnt == 0) return false;

    sort(block_vectors.begin(), block_vectors.end(), compare);

    max_x = block_vectors[0].first;
    max_y = block_vectors[0].second;
    min_x = block_vectors[0].first;
    min_y = block_vectors[0].second;
    
    for(int i=1; i<block_vectors.size(); i++){

        if(max_x < block_vectors[i].first){
            max_x = block_vectors[i].first;
        }
        if(max_y < block_vectors[i].second){
            max_y = block_vectors[i].second;
        }
        if(block_vectors[i].first < min_x){
            min_x = block_vectors[i].first;
        }
        if(block_vectors[i].first < min_y){
            min_y = block_vectors[i].second;
        }
    }
          
    rect_size = (max_x - min_x + 1) * (max_y - min_y + 1);   
    score = (rect_size + elem_cnt);
    answer_stack.push(score);
    answer += score;
    
    return true;
}

int erase_block(int ref_val, vector<pair<int, int> > &block_vectors, int prev_temp[][15])
{
    int y;
    int y_cnt;
    vector<int> y_points;

	for(int i=0; i<block_vectors.size(); i++){
		new_block[block_vectors[i].first][block_vectors[i].second] = 0;
		if(find(y_points.begin(), y_points.end(), block_vectors[i].second) == y_points.end()){
			y_points.push_back(block_vectors[i].second);		
		}
	}
	
	for(int i=0; i<y_points.size(); i++){
		int zero_cnt = 0;
		
		for(int j=2*N; j<3*N; j++){
			if(new_block[j][y_points[i]] == 0){
				zero_cnt ++;
			}		
		}
		
		while(zero_cnt){
			for(int j=(3*N-2); 0<=j; j--){
				if((new_block[j+1][y_points[i]] == 0) && (new_block[j][y_points[i]]!= 0)){
					new_block[j+1][y_points[i]] = new_block[j][y_points[i]];
					new_block[j][y_points[i]] = 0;
				}
			}
			zero_cnt --;
		}
	}
}

int solution(int block[][15])
{
    vector<int> color_v;
    static int call_cnt = 0;

    call_cnt ++;
    
    for(int i=2*N; i<3*N; i++){
        for(int j=0; j<N; j++){
            if(find(color_v.begin(), color_v.end(), block[i][j]) == color_v.end())
            {
            	if(block[i][j] != 0){
	                color_v.push_back(block[i][j]);
				}
            }
        }
    }

    vector<pair<int, int> > block_vectors_arr[color_v.size()];

    for(int i=0; i<color_v.size(); i++)
	{
		memset(visit, 0, sizeof(int)*45*15);
        
        if(get_blocks(color_v[i], block_vectors_arr[i]))
		{
            int prev_temp [45][15] = {0, };
            
            memcpy(prev_temp, new_block, sizeof(int)*45*15);
            erase_block(color_v[i], block_vectors_arr[i], prev_temp);
            if(call_cnt < 3){
                solution(new_block);
            }
            memcpy(new_block, prev_temp, sizeof(int)*45*15);
            
            if((i==(color_v.size()-1))){
            	call_cnt --;
			}
        }
        if(real_answer < answer){
            real_answer = answer;
       	}
        answer -= answer_stack.top();
        answer_stack.pop();
    }
}

int main(int argc, char** argv)
{
    cin >> N;
    memset(visit, 0, sizeof(int)*45*15);
    
    for(int i=0; i<3*N; i++){
        for(int j=0; j<N; j++){
            cin >> new_block[i][j];
        }
    }

    solution(new_block);

    cout<<real_answer;
   
    return 0;
}