글 읽기 - bfs로 풀이 반례 부탁드립니다.

goodleeches 3년 전 0

http://gooddaytocode.blogspot.... 여기서 TC 제공했던거 같은데, 사이트 개편하면서 사라진건지 TC가 안보입니다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int t;
vector<pair<int, int>> v;

void bfs(int startx, int starty, int endx, int endy)
{
	queue<pair<int, int>> q;
	q.push(make_pair(startx, starty));

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (endx == x && endy == y)
		{
			cout << "happy\n";
			return;
		}

		for (auto i = v.begin(); i != v.end();)
		{
			int xl = abs(x - i->first);
			int yl = abs(y - i->second);
			if ((xl + yl) <= 1000)
			{
				q.push(make_pair(i->first, i->second));
				i = v.erase(i);
			}
			else
				i++;
		}
	}

	cout << "sad\n";
}

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

	cin >> t;
	for (size_t testcase = 0; testcase < t; testcase++)
	{
		int n, startx, starty, endx, endy;
		cin >> n;
		cin >> startx >> starty;
		for (size_t i = 0; i < n; i++)
		{
			int x, y;
			cin >> x >> y;
			v.push_back(make_pair(x, y));
		}
		cin >> endx >> endy;
		v.push_back(make_pair(endx, endy));
		bfs(startx, starty, endx, endy);
	}

	return 0;
}

goodleeches 3년 전 0

매 테스트 케이스마다 vector 초기화를 안해줬습니다.

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

문제

문제

출처

ICPC

bfs로 풀이 반례 부탁드립니다.

goodleeches 3년 전 0

goodleeches 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말