글 읽기 - 반례좀 찾아주세용~ 0프로에서 바로 틀립니다.

kdhae1231 3년 전 0

반례좀 찾아주세요ㅜ 모든 테스트케이스 다 맞았는데 틀리게 나오네요.
/*
백준 연결

a1, a2로 가는 최단 전선 그 후 b1, b2로 가는 최단 전선

b1, b2로 가는 최단 전선 그 후 a1,a2로 가는 최단 전선.

다 찾기.

*/
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
int n, m;
int a1x, a1y, a2x, a2y;
int b1x, b1y, b2x, b2y;

struct loca {
	int x;
	int y;
};

struct point {
	int x;
	int y;
	int size;
	vector<loca> vec;
};

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

int A = 987987;
int B = 987987;
int res = 987987;

bool bfs4(vector<loca>& a, int x, int y) {
	bool check[101][101];
	memset(check, false, sizeof(check));
	for (int i = 0; i < (int)a.size(); i++)
	{
		check[a[i].x][a[i].y] = true;
	}
	vector<loca> temp;
	queue<point> que;

	que.push({ x,y,0,temp });
	check[x][y] = true;
	while (!que.empty()) {
		int cx = que.front().x;
		int cy = que.front().y;
		int size = que.front().size;

		que.pop();

		if (cx == a2x && cy == a2y) {
			A = size;
			return true;
		}

		for (int i = 0; i < 4; i++)
		{

			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && nx < n + 1 && ny >= 0 && ny < m + 1) {
				if (!check[nx][ny]) {
					check[nx][ny] = true;
					que.push({ nx,ny,size + 1,temp });
				}
			}
		}
	}
	return false;
}

void bfs3(int x, int y) {
	bool check[101][101];
	memset(check, false, sizeof(check));

	vector<loca> temp;
	temp.push_back({ x,y });
	queue<point> que;

	que.push({ x,y,0,temp });

	while (!que.empty()) {
		int cx = que.front().x;
		int cy = que.front().y;
		int size = que.front().size;
		vector<loca> memo = que.front().vec;

		que.pop();

		for (int i = 0; i < 4; i++)
		{
			vector<loca> te = memo;
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && nx < n + 1 && ny >= 0 && ny < m + 1) {
				if (nx == b2x && ny == b2y) {
					te.push_back({ nx,ny });

					if (B >= size) {
						B = size;
						if (bfs4(te, a1x, a1y)) {
							if (res > A + B) {
								res = A + B;
							}
						}
					}
				}
				else {
					if (!check[nx][ny]) {
						check[nx][ny] = true;
						te.push_back({ nx,ny });
						que.push({ nx,ny,size + 1,te });
					}
				}
			}
		}
	}
}

bool bfs2(vector<loca>& a, int x, int y) {
	bool check[101][101];
	memset(check, false, sizeof(check));

	for (int i = 0; i < (int)a.size(); i++)
	{
		check[a[i].x][a[i].y] = true;
	}

	vector<loca> temp;
	queue<point> que;

	que.push({ x,y,0,temp });
	check[x][y] = true;

	while (!que.empty()) {
		int cx = que.front().x;
		int cy = que.front().y;
		int size = que.front().size;

		que.pop();

		if (cx == b2x && cy == b2y) {
			B = size;
			return true;
		}

		for (int i = 0; i < 4; i++)
		{

			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && nx < n + 1 && ny >= 0 && ny < m + 1) {
				if (!check[nx][ny]) {
					check[nx][ny] = true;
					que.push({ nx,ny,size + 1,temp });
				}
			}
		}
	}
	return false;
}

void bfs1(int x, int y) {
	bool check[101][101];
	memset(check, false, sizeof(check));

	vector<loca> temp;
	temp.push_back({ x,y });

	queue<point> que;
	que.push({ x,y,0,temp });

	while (!que.empty()) {
		int cx = que.front().x;
		int cy = que.front().y;
		int size = que.front().size;
		vector<loca> memo = que.front().vec;

		que.pop();

		for (int i = 0; i < 4; i++)
		{
			vector<loca> te = memo;
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && nx < n + 1 && ny >= 0 && ny < m + 1) {
				if (nx == a2x && ny == a2y) {
					te.push_back({ nx,ny });

					if (A >= size) {
						A = size;

						if (bfs2(te, b1x, b1y)) {
							if (res > A + B) {
								res = A + B;
							}
						}
					}
				}
				else {
					if (!check[nx][ny]) {
						check[nx][ny] = true;
						te.push_back({ nx,ny });
						que.push({ nx,ny,size + 1,te });
					}
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> m >> n;
	cin >> a1y >> a1x >> a2y >> a2x;
	cin >> b1y >> b1x >> b2y >> b2x;

	A = B = 987987;
	bfs1(a1x, a1y);

	A = B = 987987;
	bfs3(b1x, b1y);

	if (res == 987987) {
		cout << "IMPOSSIBLE";
	}
	else {
		cout << res + 1;
	}
	return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

반례좀 찾아주세용~ 0프로에서 바로 틀립니다.

kdhae1231 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
