글 읽기 - 다리만들기 2146 - 제발 반례좀 찾아주세요 ㅜㅜ

zxwnstn 5년 전 0

하아... 100퍼센트에서 틀리는데
반례도 없고 미치겠네요 ㅜㅜ
반례만이라도 찾아주시면 감사하겠습니다..

#include<iostream>
#include<queue>
using namespace std;
int map[102][102];
int cmap[102][102];
int dx[]{ 0, 1, 0, -1 }; //상 우 하 좌
int dy[]{ -1, 0, 1, 0 };
int n;

/*
void printMap()
{
	cout << "MAP" << endl;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << map[i][j] << " ";
		cout << endl;
	}
	cout << endl;
}
*/

/*
void printCmap()
{
	cout << "CMAP" << endl;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << cmap[i][j] << " ";
		cout << endl;
	}
	cout << endl;
}
*/

bool safe(int x, int y)
{
	return ((1 <= x && x <= n) && (1 <= y && y <= n));
}

void dfs(int x, int y, int land)
{
	map[y][x] = land;
	for (int i = 0; i < 4; i++)
	{
		int nx = dx[i] + x;
		int ny = dy[i] + y;
		if (map[ny][nx] == 1 && safe(nx, ny))
			dfs(nx, ny, land);
	}
}

int bfs(queue<pair<int, int>> q)
{
	int cnt = 1;
	while (!q.empty())
	{
		int l = q.size();
		for (int i = 0; i < l; i++)
		{
			pair<int, int> temp = q.front();
			int x = temp.first;
			int y = temp.second;
			int land = map[y][x];
			q.pop();
			for (int j = 0; j < 4; j++)
			{
				int nx = dx[j] + x;
				int ny = dy[j] + y;
				if (map[ny][nx] != land && safe(nx, ny))
				{
					if (map[ny][nx] == 0)
					{
						cmap[ny][nx] = cnt;
						map[ny][nx] = land;
						q.push(make_pair(nx, ny));
					}
					else
						return cmap[y][x] + cmap[ny][nx];
				}
			}
		}
		//printMap();
		//printCmap();
		cnt++;
	}
}


int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> map[i][j];

	int land = 2;  
	//dfs로 각각의 섬 고유번호 초기화
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] == 1)
			{
				dfs(j, i, land);
				land++;
			}
		}
	}
	//printMap();

	//시작점 q에 담기
	queue<pair<int, int>> q;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (map[i][j] != 0)
				q.push(make_pair(j, i));
		}
	}

	int ans = bfs(q);
	cout << ans << endl;
	//system("pause");
	return 0;
}

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

문제

문제

출처

ICPC

다리만들기 2146 - 제발 반례좀 찾아주세요 ㅜㅜ

zxwnstn 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말