글 읽기 - 93%에서 틀렸습니다가 나와요..

cleankid99 5년 전 0

당연히 예제는 다 통과했구요.

질문게시판에 올라와있는 반례들도 여러개 넣어봤어요

93퍼센트에서 틀렸다고 나오는데

알고리즘 상에 어떠한 오류가 있는지 한번 봐주실 수 있을까요?

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

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

vector<vector<int> > v;
vector<vector<int> > dist;
queue<pair<int, int> > q;

int m, n, M = 0; // M은 최대값, 최대값을 저장해서 출력

void bfs() {
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		int temp = dist[x][y]; 
		dist[x][y] = 1; // dist[x][y]를 방문했다고 기록을 남김
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x, ny = y;
			nx += dx[i];
			ny += dy[i];

			if (nx >= 0 && nx < m && ny >= 0 && ny < n && v[nx][ny] == -1) { dist[nx][ny] = -1; }

			if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] == -2 && v[nx][ny] != -1) {
				q.push(make_pair(nx, ny));
				dist[nx][ny] = temp + 1;
				if (M < dist[nx][ny]) {
					M = dist[nx][ny];
				}
			}

		}

	}
}

int main() {
	int temp;
	cin >> n >> m;
	v.resize(m + 1);
	dist.resize(m + 1);

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> temp;
			v[i].push_back(temp);
			if (temp == -1) {
				dist[i].push_back(-1);
			}
			else {
				dist[i].push_back(-2); // dist를 -2(쓰레기값)로 초기화
			}

			if (temp == 1) {
				q.push(make_pair(i, j));
				dist[i][j] = 0;
			}

		}
	}
	bfs();

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (dist[i][j] == 0) { // 만약 dist가 0이라면(방문하지않았다면)
				cout << -1 << '\n';
				return 0;
			}
		}
	}

	cout << M << '\n';

	return 0;
}

evenharder 5년 전 1

처음에 익은 토마토가 하나도 없을 때 처리가 안 되어 있는 것 같습니다.

Input:
2 2
0 0
0 0

Output:
-1

evenharder 5년 전 1

다시 보니 예제 2에 대한 답이 나오지 않는 것 같습니다. 현재 코드는 익은 토마토와 연결되어 있지 않은 익지 않은 토마토를 익은 토마토처럼 간주하는 것으로 보입니다.

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

문제

문제

출처

ICPC

93%에서 틀렸습니다가 나와요..

cleankid99 5년 전 0

evenharder 5년 전 1

evenharder 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말