글 읽기 - 아기상어 질문드립니다.

jjohye11 5년 전 0

문제의 예제와 게시판의 반례들을 실행시켰을 땐 성공하지만, 문제를 제출하면 계속 틀렸습니다가 뜹니다.

어느 부분을 놓치고 있는지 도저히 감이 오지 않아서 도움 요청드립니다 ㅠㅠ

코드에 대한 따끔한 충고도 감사히 받겠습니다!

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

#define MAX_SIZE 12
#define EMPTY 0
#define EAT -1

int N, M;
int map[MAX_SIZE][MAX_SIZE];
int visit[MAX_SIZE][MAX_SIZE];
int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

struct fish {
	int y, x, size, i;
};
vector<fish> fishs; //물고기 정보
fish temp;

struct baby {
	int y, x, size, time;
};
baby shark; //아기상어 정보

struct path {
	int y, x;
};
queue<path> timer; //시간 측정에 사용

int eatting = 0;
int checkTime(int fy, int fx, int sy, int sx, int time) {

	while (!timer.empty())
		timer.pop();

	timer.push({ sy, sx });

	while (!timer.empty()) {
		int nowy, nowx;
		nowy = timer.front().y;
		nowx = timer.front().x;
		timer.pop();

		if (nowy == fy && nowx == fx) {
			break;
		}

		for (int i = 0; i < 4; i++) {
			int nexty, nextx;
			nexty = nowy + dir[i][0];
			nextx = nowx + dir[i][1];

			if (visit[nexty][nextx] != 0 || shark.size < map[nexty][nextx] || 0 > nexty || nexty >= N || 0 > nextx || nextx >= N) {
				if (map[nexty][nextx] != 9) {
					continue;
				}
			}
			visit[nexty][nextx] = visit[nowy][nowx] + 1;
			timer.push({ nexty, nextx });
		}
	}
	return visit[fy][fx];
}

void storeNewLocation(int i, int y, int x, int size) {
	temp.i = i;
	temp.y = y;
	temp.x = x;
	temp.size = size;
}

bool iseat = false;
void search() {
	if (fishs.size() == 0)
		return;

	int sY, sX, sSize, sTime;

	sY = shark.y;
	sX = shark.x;
	sSize = shark.size;
	sTime = shark.time;

	int near = 987654321;
	iseat = false;
	for (int i = 0, size = fishs.size(); i < size; i++) {
		int fY, fX, fSize;

		fY = fishs.at(i).y;
		fX = fishs.at(i).x;
		fSize = fishs.at(i).size;

		if (map[fY][fX] != EAT && fSize < sSize) {
			int visitcount;
			visitcount = checkTime(fY, fX, sY, sX, 0);

			if (visitcount == 0) {
				continue;
			}

			if (near >= visitcount) {
				if (near == visitcount) {
					if (fY <= temp.y) {
						if (fY == temp.y) {
							if (fX < temp.x) {
								storeNewLocation(i, fY, fX, fSize);
								near = visitcount;
							}
						}
						else {
							storeNewLocation(i, fY, fX, fSize);
							near = visitcount;
						}
					}
				}
				else {
					storeNewLocation(i, fY, fX, fSize);
					near = visitcount;
					iseat = true;
				}
			}
		}
		memset(visit, 0, sizeof(visit));
	}

	if (iseat) {
		eatting++;
		shark.y = temp.y;
		shark.x = temp.x;
		shark.time = shark.time + near;
		map[shark.y][shark.x] = EAT;

		if (eatting == shark.size) {
			shark.size = shark.size + 1;
			eatting = 0;
		}

		fishs.erase(fishs.begin()+temp.i); //물고기의 i 값은 삭제를 위해 사용
	}
	else {
		return;
	}
	search();
}

int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int a;
			cin >> a;

			if (a == 9) {
				shark = { i, j, 2, 0 };
			}
			if (0 < a && a <= 6) {
				fishs.push_back({ i, j, a, 0 });
			}

			map[i][j] = a;
		}
	}
	search();

	cout << shark.time << endl;
	return 0;
}

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

문제

문제

출처

ICPC

아기상어 질문드립니다.

jjohye11 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말