글 읽기 - [반례]틀렸다고 나오는데 반례를 찾고싶습니다.(슈도코드 써놨습니다!!)

hong4243 6년 전 0

int count() ; 섬의 개수를 찾아주는 함수

main(){

while(1){

1. 만약 섬의 개수가 1이상이면 탈출 후 결과출력

2. 섬이 모두 녹아버렸을 때 0출력

3. 섬을 한번씩 줄여서 tmpMap[][]에 저장

4.. 줄인섬을 다신 메인 map[][]으로 이동

}

#include <stdio.h>
#pragma warning(disable:4996)

void input();
int check(int x, int y);

int n, m;
int map[102][102];
int tmpMap[102][102];
int visit[102][102] = {0};

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

int q[100000][2];
int front = 0, rear = 0;
int tmpX, tmpY;
int currentX, currentY;
int result = 0;;
int cnt = 0;

int count(){
	front = 0, rear = 0;
	int cnt = 0;

	for (int i = 0; i < n; i++) {
		if (cnt > 1) {
			break;
		}
		for (int j = 0; j < m; j++) {
			if (cnt > 1) {
				break;
			}
			if (map[i][j] > 0 && visit[i][j] ==0) {
				q[rear][0] = i;
				q[rear][1] = j;
				rear++;
				cnt++;
				//printf("cnt(%d,%d) = %d\n", i, j, cnt);
				visit[i][j] = 1;
				while (front < rear) {
					currentX = q[front][0];
					currentY = q[front][1];
					front++;
					
					for (int i = 0; i < 4; i++) {
						tmpX = currentX + dirX[i];
						tmpY = currentY + dirY[i];
						//printf("map(%d,%d) = %d  visit = %d\n", tmpX, tmpY, map[tmpX][tmpY], visit[tmpX][tmpY]);
						if (check(tmpX, tmpY) && map[tmpX][tmpY] > 0 && visit[tmpX][tmpY] == 0) {
							
							q[rear][0] = tmpX;
							q[rear][1] = tmpY;
							rear++;
							visit[tmpX][tmpY] = 1;
						}
					}				
				}			
			}
		}
	}
	return cnt;
}

int main()
{
	int printFlag = 0;
	input();
	
	while (1){
		int flag = count();
		if (flag> 1) {
			break;
		}
		result++;

		int sum = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				sum += map[i][j];
			}
		}
		if (sum == 0) {
			printf("0");
			printFlag++;
			break;
		}

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

				if (map[i][j] > 0) {
					for (int k = 0; k < 4; k++) {
						
						if (map[i + dirX[k]][j + dirY[k]] <= 0 && check(i + dirX[k], j + dirY[k])) {
							cnt++;
						}
						tmpMap[i][j] = map[i][j] - cnt;
						if (tmpMap[i][j] < 0) {
							tmpMap[i][j] = 0;
						}
					}
				}
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = tmpMap[i][j];
				visit[i][j] = 0;
			}
		}
	}
	
	if (printFlag == 0) {
		printf("%d", result);
	}
	
}

void input()
{

	scanf("%d %d", &n,&m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d",&map[i][j]);
			tmpMap[i][j] = map[i][j];
		}
	}


}

int check(int x, int y) {

	if (x >= 0 && x < n && y >= 0 && y < m) {
		return 1;
	}
	else {
		return 0;
	}

}

djm03178 6년 전 1

문제 조건을 잘 읽으셔야 됩니다.

"첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다."

따라서, 맵의 크기도 최소 300x300이어야 합니다.

hong4243 6년 전 0

감사합니다!! 문제 해결했습니다!

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

문제

문제

출처

ICPC

[반례]틀렸다고 나오는데 반례를 찾고싶습니다.(슈도코드 써놨습니다!!)

hong4243 6년 전 0

djm03178 6년 전 1

hong4243 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말