글 읽기 - 반례 좀 제발제발제발 찾아주세요...

jjssu1672 5년 전 0

예제 케이스, N=20인 경우, 상어가 움직일 수 없는 경우 모두 체크해 보았고, 과정도 출력해봤습니다. 그런데 틀렸다고 나옵니다..반례를 찾아주시면 정말 감사하겠습니다.

제가 짠 방법은 BFS를 이용해 상어 위치에서 먹을 수 있는 모든 물고기를 벡터에 저장한 다음, 조건에 맞는(가장 가깝고, 가장 위/왼쪽에 있는) 좌표를 선택해 이동하고 다시 BFS를 반복하는 코드입니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dir[4][2] = { { -1,0 },{ 0,-1 },{ 0,1 },{ 1,0 } }; //위 좌 우 아래
int map[22][22];
int visit[22][22]; //거리
int N, shark = 2; //size, shark size
int eaten, T; //먹은 수, 시간
pair<int, int> sharkLocation;
vector<pair<int, pair<int, int> > > next_fish;// = make_pair(-1, -1);

bool boundaryCheck(int r, int c) {
	if (r < 0 || r >= N || c < 0 || c >= N) return false;
	else return true;
}
void move(pair<int, int> d, pair<int, int> s) { //move and eat
	T += visit[d.first][d.second]; //시간 증가
	map[d.first][d.second] = 0; //목적지 값 0
	eaten++; //먹은 물고기 수 증가
	sharkLocation = d; //상어 위치 이동
	if (eaten == shark) {
		shark++; //상어 크기 증가
		eaten = 0;
		//printf("shark size is %d\n", shark);
	}
	//printf("shark move from (%d, %d) to (%d, %d) T=%d\n", s.first, s.second, d.first, d.second,T);
	/*for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}*/
}

void search_bfs(pair<int, int> start, int shark_size) {
	int r, c, R, C;
	queue<pair<int, int> > q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			visit[i][j] = -1; //visit 초기화
	}
	q.push(start);
	visit[start.first][start.second] = 0; 
	while (!q.empty()) {
		R = q.front().first;
		C = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			r = dir[i][0] + R;
			c = dir[i][1] + C;
			if (boundaryCheck(r, c) && visit[r][c] == -1 && map[r][c] <= shark_size) { //이동할 수 있다.
				q.push(make_pair(r, c));
				visit[r][c] = visit[R][C] + 1;
				if (map[r][c] > 0 && map[r][c] < shark_size) {//먹을 수 있다.
					next_fish.push_back(make_pair(visit[r][c],make_pair(r, c)));//거리와 좌표 저장
				}
			}
			else;
		}
	}
}

void solve(pair<int, int> start) {
	/*
	1. 상어 위치로부터 먹을 수 있는 가장 가까운 물고기(next_fish)를 탐색
	2. 먹을 수 있는 물고기가 존재하는 경우 move
	3. 다음 위치 초기화
	4. 1,2,3 반복
	*/
	search_bfs(sharkLocation, shark); //상어 위치에서 가장 가까운 물고기를 찾음
	while (next_fish.size()!=0) {
		pair<int,int> nextFish=next_fish.front().second;
		//먹을 수 있는 물고기 중 가장 가까운 곳 탐색
		pair<int, pair<int,int> > nearest = next_fish.at(0); // 가장 가까운 거리
		for (int i = 1; i < next_fish.size(); i++) {
			if (next_fish.at(i).first < nearest.first) { // 거리가 더 가깝다.
				nextFish = make_pair(next_fish.at(i).second.first, next_fish.at(i).second.second);
			}
			else if (next_fish.at(i).first == nearest.first) { //거리가 똑같다.
				if (next_fish.at(i).second.first < nearest.second.first) { // 위에 있다.
					nextFish = make_pair(next_fish.at(i).second.first, next_fish.at(i).second.second);
				}
				else if (next_fish.at(i).second.first == nearest.second.first) { // 같은 높이다.
					if (next_fish.at(i).second.second < nearest.second.second) { //왼쪽에 있다.
						nextFish = make_pair(next_fish.at(i).second.first, next_fish.at(i).second.second);
					}
				}
			}
		}
		move(nextFish, sharkLocation); //가장 가까운 1로 이동.
		next_fish.clear(); //다음 위치 초기화
		search_bfs(sharkLocation, shark); //다음 상어 위치에서 가장 가까운 물고기를 찾음.
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if(map[i][j] == 9) {
				sharkLocation = make_pair(i, j); //상어 위치 저장
				map[i][j] = 0; //상어 위치는 0으로 바꿈
			}
		}
	}
	solve(sharkLocation);
	cout << T;
	return 0;
}

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

문제

문제

출처

ICPC

반례 좀 제발제발제발 찾아주세요...

jjssu1672 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말