글 읽기 - 12100 게시판 반레는 대부분 통과했습니다만...도움주시면 감사하겠습니다.

david921 3년 전 0

https://www.acmicpc.net/board/...

에 제시된 반례들은 전부 맞다고 나옵니다.

주석은 up방향으로 움직이는 것에 대해 주로 달았습니다.

기본적인 생각은 움직일 벽 쪽부터 채워나가는 방식으로, 이동과 합쳐지는 것을 함께 고려했습니다.

#include<iostream>

using namespace std;

int n;
int **map;
int **visit; 

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

void DFS(int iter);
void clean_visit(void);

int max_block = 0;

int main(void)
{
	cin >> n;
	
	map = new int*[n];
	visit = new int*[n];
	
	for(int i = 0; i < n; i++){
		map[i] = new int[n];
		visit[i] = new int[n];
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> map[i][j];
		}
	}
	
	DFS(5);
	
	for(int i = 0; i < n; i++){
		delete map[i];
		delete visit[i];
	}
	
	delete map;
	delete visit;
	
	cout << max_block << endl;

	return 0;
}

void DFS(int iter){
	if(iter > 0){
		int **tmpmap;
		
		tmpmap = new int*[n];
		
		for(int i = 0; i < n; i++){
			tmpmap[i] = new int[n];
		}
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				tmpmap[i][j] = map[i][j];
			}
		}
		
		//up 
		clean_visit();
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				int x_pos = i;
				int y_pos = j;
				int done = 0;
				
				if(map[x_pos][y_pos] == 0){
					done = 1;
				}
				
				//자리 찾기 위해 while으로 수행. 0인 경우 이동할 필요 없으므로 자리 찾기 수행안함. 
				while(done == 0){
					//이동 가능한지 확인 
					if(x_pos + dx[0] > -1 && x_pos + dx[0] < n && y_pos + dy[0] > -1 && y_pos + dy[0] < n){
						//비어있어서 움직일 수 있는 곳인지 확인 
						if(map[x_pos + dx[0]][y_pos + dy[0]] == 0){
							map[x_pos + dx[0]][y_pos + dy[0]] = map[x_pos][y_pos];
							visit[x_pos + dx[0]][y_pos + dy[0]] = visit[x_pos][y_pos];
							map[x_pos][y_pos] = 0;
							visit[x_pos][y_pos] = 0;
							x_pos = x_pos + dx[0];
							y_pos = y_pos + dy[0];
						}
						//합쳐진 적이 없고, 자신도 합쳐지지 않았고, 자신과 같은 수 인경우 
						else if(map[x_pos + dx[0]][y_pos + dy[0]] == map[x_pos][y_pos] && visit[x_pos + dx[0]][y_pos + dy[0]] == 0 && visit[x_pos][y_pos] == 0){
							map[x_pos + dx[0]][y_pos + dy[0]] = 2 * map[x_pos + dx[0]][y_pos + dy[0]];
							visit[x_pos + dx[0]][y_pos + dy[0]] = 1;
							map[x_pos][y_pos] = 0;
							visit[x_pos][y_pos] = 0;
							done = 1;
						}
						else{
							done = 1;
						}
					}
					else{
						done = 1;
					}
				}
			}
		}
		
		//반복횟수 줄여서 DFS 
		DFS(iter - 1);
		
		//보드 초기화 
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				map[i][j] = tmpmap[i][j];
			}
		}
		
		
		//down
		clean_visit();
		
		for(int i = n - 1; i >= 0; i--){
			for(int j = 0; j < n; j++){
				int x_pos = i;
				int y_pos = j;
				int done = 0;
				
				if(map[x_pos][y_pos] == 0){
					done = 1;
				}

				while(done == 0){
					if(x_pos + dx[2] > -1 && x_pos + dx[2] < n && y_pos + dy[2] > -1 && y_pos + dy[2] < n){
						if(map[x_pos + dx[2]][y_pos + dy[2]] == 0){
							map[x_pos + dx[2]][y_pos + dy[2]] = map[x_pos][y_pos];
							visit[x_pos + dx[2]][y_pos + dy[2]] = visit[x_pos][y_pos];
							map[x_pos][y_pos] = 0;
							visit[x_pos][y_pos] = 0;
							x_pos = x_pos + dx[2];
							y_pos = y_pos + dy[2];
						}
						else if(map[x_pos + dx[2]][y_pos + dy[2]] == map[x_pos][y_pos] && visit[x_pos + dx[2]][y_pos + dy[2]] == 0 && visit[x_pos][y_pos] == 0){
							map[x_pos + dx[2]][y_pos + dy[2]] = 2 * map[x_pos + dx[2]][y_pos + dy[2]];
							visit[x_pos + dx[2]][y_pos + dy[2]] = 1;
							map[x_pos][y_pos] = 0;
							visit[x_pos][y_pos] = 0;
							done = 1;
						}
						else{
							done = 1;
						}
					}
					else{
						done = 1;
					}
				}
			}
		}
		
		DFS(iter - 1);
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				map[i][j] = tmpmap[i][j];
			}
		}
		
		//right
		clean_visit();
		
		for(int j = 0; j < n; j++){
			for(int i = 0; i < n; i++){
				int x_pos = i;
				int y_pos = j;
				int done = 0;
				
				if(map[x_pos][y_pos] == 0){
					done = 1;
				}

				while(done == 0){
					if(x_pos + dx[1] > -1 && x_pos + dx[1] < n && y_pos + dy[1] > -1 && y_pos + dy[1] < n){
						if(map[x_pos + dx[1]][y_pos + dy[1]] == 0){
							map[x_pos + dx[1]][y_pos + dy[1]] = map[x_pos][y_pos];
							visit[x_pos + dx[1]][y_pos + dy[1]] = visit[x_pos][y_pos];
							map[x_pos][y_pos] = 0;
							visit[x_pos][y_pos] = 0;
							x_pos = x_pos + dx[1];
							y_pos = y_pos + dy[1];
						}
						else if(map[x_pos + dx[1]][y_pos + dy[1]] == map[x_pos][y_pos] && visit[x_pos + dx[1]][y_pos + dy[1]] == 0 && visit[x_pos][y_pos] == 0){
							map[x_pos + dx[1]][y_pos + dy[1]] = 2 * map[x_pos + dx[1]][y_pos + dy[1]];
							visit[x_pos + dx[1]][y_pos + dy[1]] = 1;
							map[x_pos][y_pos] = 0;
							visit[x_pos][y_pos] = 0;
							done = 1;
						}
						else{
							done = 1;
						}
					}
					else{
						done = 1;
					}
				}
			}
		}
		
		DFS(iter - 1);
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				map[i][j] = tmpmap[i][j];
			}
		}
		
		//left
		clean_visit();
		
		for(int j = n - 1; j >= 0; j--){
			for(int i = 0; i < n; i++){
				int x_pos = i;
				int y_pos = j;
				int done = 0;
				
				if(map[x_pos][y_pos] == 0){
					done = 1;
				}

				while(done == 0){
					if(x_pos + dx[3] > -1 && x_pos + dx[3] < n && y_pos + dy[3] > -1 && y_pos + dy[3] < n){
						if(map[x_pos + dx[3]][y_pos + dy[3]] == 0){
							map[x_pos + dx[3]][y_pos + dy[3]] = map[x_pos][y_pos];
							visit[x_pos + dx[3]][y_pos + dy[3]] = visit[x_pos][y_pos];
							map[x_pos][y_pos] = 0;
							visit[x_pos][y_pos] = 0;
							x_pos = x_pos + dx[3];
							y_pos = y_pos + dy[3];
						}
						else if(map[x_pos + dx[3]][y_pos + dy[3]] == map[x_pos][y_pos] && visit[x_pos + dx[3]][y_pos + dy[3]] == 0 && visit[x_pos][y_pos] == 0){
							map[x_pos + dx[3]][y_pos + dy[3]] = 2 * map[x_pos + dx[3]][y_pos + dy[3]];
							visit[x_pos + dx[3]][y_pos + dy[3]] = 1;
							map[x_pos][y_pos] = 0;
							visit[x_pos][y_pos] = 0;
							done = 1;
						}
						else{
							done = 1;
						}
					}
					else{
						done = 1;
					}
				}
			}
		}
		
		DFS(iter - 1);
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				map[i][j] = tmpmap[i][j];
			}
		}
		
		//end
		for(int i = 0; i < n; i++){
			delete tmpmap[i];
		}
		
		delete tmpmap;
	}
	else{
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(map[i][j] > max_block){
					max_block = map[i][j];
				}
			}
		}
	}
}

void clean_visit(void){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			visit[i][j] = 0;
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

12100 게시판 반레는 대부분 통과했습니다만...도움주시면 감사하겠습니다.

david921 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말