글 읽기 - C++/ 반례가 무엇일까요?? ㅠㅠ

pppp1923 3년 전 0

질문글의 반례와 테케는 모두 값이 나오는데 1%에서 통과를 못하네요ㅠㅠ
무엇이 문제일까요??? ㅠㅠ
#include <iostream>
#include <algorithm>
using namespace std;

int n, m, k;
int arr[21][21];
pair<int, int> smell[21][21]; // first: shark_index, second: smell_count
int shark_dir_prior[402][4][4];
pair<int, int> shark_current_pos[402];
int shark_current_dir[402];
bool shark_range_out[402];
int dr[] = { -1,1,0,0 };
int dc[] = { 0,0,-1,1 };
int ans;

bool finish_check() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] != 0 && arr[i][j] != 1) {
				return false;
			}
		}
	}
	return true;
}

bool range_check(int r, int c) {
	if (0 <= r && r < n && 0 <= c && c < n) return true;
	else return false;
}

void smell_update() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (smell[i][j].first != 0) {
				if (smell[i][j].second == 1) { // 냄새삭제
					smell[i][j].first = 0;
					smell[i][j].second = 0;
				}
				else { // 냄새 감소
					smell[i][j].second--;
				}
			}
		}
	}
	// 냄새 등록
	for (int shark_index = 1; shark_index <= m; shark_index++) {
		if (shark_range_out[shark_index] == true) continue;
		smell[shark_current_pos[shark_index].first][shark_current_pos[shark_index].second].second = k;
	}
}

void go() {
	for (int shark_index = 1; shark_index <= m; shark_index++) {
		if (shark_range_out[shark_index] == true) continue;

		int current_dir = shark_current_dir[shark_index];
		int current_r = shark_current_pos[shark_index].first;
		int current_c = shark_current_pos[shark_index].second;
		bool dont_smell = false;
		for (int k = 0; k < 4; k++) {
			int next_dir = shark_dir_prior[shark_index][current_dir][k];
			int next_r = current_r + dr[next_dir];
			int next_c = current_c + dc[next_dir];
			if (range_check(next_r, next_c) == true) {
				if (smell[next_r][next_c].second == 0) { // 냄새가 없는 곳
					dont_smell = true;

					if (arr[next_r][next_c] != 0) { // 다른 상어가 있으면
						// 이동중인 상어의 번호가 더 작은 경우
						if (shark_index < arr[next_r][next_c]) {
							arr[next_r][next_c] = shark_index;
							smell[next_r][next_c].first = shark_index;
							shark_current_dir[shark_index] = next_dir;
							shark_current_pos[shark_index].first = next_r;
							shark_current_pos[shark_index].second = next_c;
							arr[current_r][current_c] = 0;
							shark_range_out[arr[next_r][next_c]] = true; // 숫자 높은 상어를 격자 밖으로
						}
						// 원래 next 자리에 있던 상어의 번호가 더 작은 경우
						else {
							arr[current_r][current_c] = 0;
							shark_range_out[shark_index] = true;
						}
					}
					else { // 다른 상어 없으면 next로 이동
						arr[next_r][next_c] = shark_index;
						smell[next_r][next_c].first = shark_index;
						shark_current_dir[shark_index] = next_dir;
						shark_current_pos[shark_index].first = next_r;
						shark_current_pos[shark_index].second = next_c;
						arr[current_r][current_c] = 0;
					}

					break;
				}
			}
		}
		// 주변에 냄새가 없는 곳이 없으면 자신의 냄새가 있는 곳으로 이동
		if (dont_smell == false) {
			for (int k = 0; k < 4; k++) {
				int next_dir = shark_dir_prior[shark_index][current_dir][k];
				int next_r = current_r + dr[next_dir];
				int next_c = current_c + dc[next_dir];
				if (range_check(next_r, next_c) == true) {
					if (smell[next_r][next_c].first == shark_index) { // 자신의 냄새가 있는 곳
						if (arr[next_r][next_c] != 0) { // 다른 상어가 있으면
							// 이동중인 상어의 번호가 더 작은 경우
							if (shark_index < arr[next_r][next_c]) {
								arr[next_r][next_c] = shark_index;
								smell[next_r][next_c].first = shark_index;
								shark_current_dir[shark_index] = next_dir;
								shark_current_pos[shark_index].first = next_r;
								shark_current_pos[shark_index].second = next_c;
								arr[current_r][current_c] = 0;
								shark_range_out[arr[next_r][next_c]] = true; // 숫자 높은 상어를 격자 밖으로
							}
							// 원래 next 자리에 있던 상어의 번호가 더 작은 경우
							else {
								arr[current_r][current_c] = 0;
								shark_range_out[shark_index] = true;
							}
						}
						else { // 다른 상어 없으면 next로 이동
							arr[next_r][next_c] = shark_index;
							smell[next_r][next_c].first = shark_index;
							shark_current_dir[shark_index] = next_dir;
							shark_current_pos[shark_index].first = next_r;
							shark_current_pos[shark_index].second = next_c;
							arr[current_r][current_c] = 0;
						}

						break;
					}
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] != 0) {
				int shark_index = arr[i][j];
				smell[i][j].first = shark_index;
				smell[i][j].second = k;
				shark_current_pos[shark_index].first = i;
				shark_current_pos[shark_index].second = j;
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		int dir; cin >> dir;
		shark_current_dir[i] = dir - 1;
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				int dir; cin >> dir;
				shark_dir_prior[i][j][k] = dir - 1;
			}
		}
	}

	//for (ans = 1; ans < 1001; ans++) {
	//	go();
	//	smell_update();

	//	/*cout << "count " << ans<<" \n";
	//	for (int i = 0; i < n; i++) {
	//		for (int j = 0; j < n; j++) {
	//			cout << arr[i][j] << " ";
	//		}
	//		cout << "\n";
	//	}

	//	cout << "\n";
	//	for (int i = 0; i < n; i++) {
	//		for (int j = 0; j < n; j++) {
	//			cout << smell[i][j].first << " ";
	//		}
	//		cout << "\n";
	//	}

	//	cout << "\n";
	//	for (int i = 0; i < n; i++) {
	//		for (int j = 0; j < n; j++) {
	//			cout << smell[i][j].second << " ";
	//		}
	//		cout << "\n";
	//	}
	//	cout << "\n";*/

	//	if (finish_check() == true) break;
	//}

	while (ans < 1000) {
		ans++;
		go();
		smell_update();
		if (finish_check() == true) {
			cout << ans << "\n";
			return 0;
		}
	}

	cout << "-1\n";

	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

C++/ 반례가 무엇일까요?? ㅠㅠ

pppp1923 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
