글 읽기 - 반례 좀 찾아주세요ㅜㅜ

icd0422 2년 전 0

예제 테스트는 다 잘 나오는데 오답 뜹니다.

도저히 반례를 못찾겠습니다 .ㅠㅠㅠㅠ

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

using namespace std;

int map[21][21];
int visit[21][21];

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

int n;

pair<int, int> shark_pos, shortfish_pos;
vector<pair<int, int> > v;

int shark_size = 2;
int eat_count;
int fish_count;

queue<pair<int, int> > q;

int main()
{
	shortfish_pos.first = 30;
	shortfish_pos.second = 30;

	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)
			{
				shark_pos.first = i;
				shark_pos.second = j;
			}

			else if (map[i][j] != 0)
			{
				fish_count++;
			}
		}
	}

	int t = 0;
	int tt = 0;

	while (1)
	{
		if (fish_count == 0) break;

		q.push(shark_pos);
		visit[shark_pos.first][shark_pos.second] = 1;
		tt = t;

		while (!q.empty())
		{
			int size = q.size();

			int k = 0;

			while (size--)
			{
				int x = q.front().first;
				int y = q.front().second;
				q.pop();

				if (1 <= map[x][y] && map[x][y] < shark_size)//물고기를 먹었을 때
				{
					v.push_back(make_pair(x, y));
					k = 1;
				}

				else//그냥 통과 경로일 때
				{
					if (k == 0)//먹을 수 있는 물고기가 없을 때만
					{
						for (int i = 0; i < 4; i++)
						{
							int mx = x + dx[i];
							int my = y + dy[i];
							if (mx < 0 || my < 0 || mx >= n || my >= n || (map[mx][my] > shark_size) || visit[mx][my]) continue;

							q.push(make_pair(mx, my));
							visit[mx][my] = 1;

						}
					}
				}

			}

			if (q.size() == 0 && v.size() == 0)
			{
				cout << tt;
				return 0;
			}

			for (int i = 0; i < v.size(); i++)
			{
				if (v[i].first < shortfish_pos.first)
				{
					shortfish_pos = v[i];
				}

				else if (v[i].first == shortfish_pos.first)
				{
					if (v[i].second < shortfish_pos.second)
					{
						shortfish_pos = v[i];
					}
				}
			}

			if (v.size() == 0)
			{
				t++;
				continue;
			}

			map[shark_pos.first][shark_pos.second] = 0;
			shark_pos = shortfish_pos;
			map[shark_pos.first][shark_pos.second] = 9;
			fish_count--;
			eat_count++;
			if (eat_count == shark_size)
			{
				shark_size++;
				eat_count = 0;
			}

			while (!q.empty())
			{
				q.pop();
			}
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					visit[i][j] = 0;
				}
			}

			v.clear();
			shortfish_pos.first = 30;
			shortfish_pos.second = 30;
			break;

		}
	}

	cout << t;
	return 0;
}

joonas 2년 전 0

개복치의 크기는 9보다 커질 수 있습니다.

//Line:127
// map[shark_pos.first][shark_pos.second] = 9;
map[shark_pos.first][shark_pos.second] = 0;

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

문제

문제

출처

ICPC

반례 좀 찾아주세요ㅜㅜ

icd0422 2년 전 0

joonas 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말