글 읽기 - [반례] 틀렸다고 나오는데 반례를 찾고 싶습니다!!

hong4243 6년 전 0

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

--> 8

6 4
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

6 4
1 1 1 1 1 1
1 1 -1 1 1 1
1 -1 0 -1 1 1
1 1 -1 1 1 1

돌려본 테스트 케이스는 이거고요!!! 어떤점에서 틀렸다고 나오는지 알고 싶습니다.!!!

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

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

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

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

int q[1000000][2];
int front = 0, rear = 0;
int currentX, currentY;
int tmpX, tmpY;

int result = 0;

int main()
{
	int flag = 0;
	input();
	int tmp = mapCheck();
	if (tmp == 0) {
		flag++;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1 && visit[i][j] == 0) {
			
				q[rear][0] = i;
				q[rear][1] = j;
				rear++;
				visit[i][j] = 1;
			}
		}
	}

	while (front <rear) {

		currentY = q[front][0];
		currentX = q[front][1];
		front++;

		for (int k = 0; k < 4; k++) {
			tmpY = currentY + dirY[k];
			tmpX = currentX + dirX[k];
			if (check(tmpY, tmpX) == 1 && map[tmpY][tmpX] == 0) {
				q[rear][0] = tmpY;
				q[rear][1] = tmpX;
				rear++;
				visit[tmpY][tmpX] = visit[currentY][currentX] + 1;
			}
		}

	}
	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			printf("%d ", visit[i][j]);
		}
		printf("\n");
	}
	printf("\n\n\n");
	*/
	if (flag == 1) {
		printf("0");
	}
	else if (flag == 0 ) {
		result = maxVisit();
		printf("%d", result-1);
	
	}

}

int maxVisit()
{

	int max=0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == 0) {
				return 0;
			}
			if (max < visit[i][j]) {
				max = visit[i][j];
			}
		}
	}
	return max;

}

int mapCheck() {//하나라도 안익어 있으면 1;
				//모두 익어있으면 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0) {
				return 1;
			}
		}
	}

	return 0;
}

int check(int y, int x) {

	if (y >= 0 && y < n&&x >= 0 && x < m && visit[y][x] == 0) {
		return 1;
	}
	else {
		return 0;
	}
}
void input()
{
	scanf("%d %d", &m, &n);

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

/*

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

--> 8

6 4
1 1 1 1 1 1 
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

6 4
1 1 1 1 1 1
1 1 -1 1 1 1
1 -1 0 -1 1 1
1 1 -1 1 1 1

*/

djm03178 6년 전 1

3 3

1 0 0

-1 -1 0

0 0 0

이건 토마토가 모두 익을 수 있습니다.

hong4243 6년 전 1

감사합니다!!! 마지막에 체크할때

이렇게 변경하니깐 해결 되네요!!

int maxVisit()
{

	int max=0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == 0 && map[i][j] ==0) {
				return 0;
			}
			if (max < visit[i][j]) {
				max = visit[i][j];
			}
		}
	}
	return max;

}

hong4243 6년 전 0

감사합니다!!!!

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

문제

문제

출처

ICPC

[반례] 틀렸다고 나오는데 반례를 찾고 싶습니다!!

hong4243 6년 전 0

djm03178 6년 전 1

hong4243 6년 전 1

hong4243 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말