글 읽기 - 반례를 찾을 수 없어 도움을 요청드립니다.

wjd5126 1년 전 0

도저히 반례를 못찾아서 질문드립니다.

어떤 경우에 문제가 생길까요...?

도와주세요...

0%에서 틀립니다 뜨네요...

제발...

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

using namespace std;
struct point {
	int y = 0;
	int x = 0;
	int time = 0;
	bool operator < (const point& a)const {
		if (time == a.time) {
			if (y == a.y) {
				return x > a.x;
			}
			else return y > a.y;
		}
		else return time > a.time;
	}
};

int map[23][23] = { 0 };

vector<point> people[23][23];
point me;
int bn, bm;
int score;

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

void input() {
	cin >> bn >> bm >> score;
	for (int i = 1; i <= bn; i++) {
		for (int j = 1; j <= bn; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) map[i][j] = -1;
		}
	}
	cin >> me.y >> me.x;
	for (int i = 0; i < bm; i++) {
		int sy, sx, ey, es;
		cin >> sy >> sx >> ey >> es;
		people[sy][sx].push_back({ ey,es,0 });
	}
}

//우선순위 큐 + bfs로 가장 가까운 손님 탐색
point find_people() {
	int visualmap[23][23] = { 0 };
	copy(&map[0][0], &map[0][0] + 23 * 23, &visualmap[0][0]);
	priority_queue<point>arr;
	arr.push(me);
	visualmap[me.y][me.x] = -2;

	bool check = 1;
	//출발지 == 손님인 경우
	if (!people[me.y][me.x].empty()) { check = 0; me.time = 0; }
	
	//bfs
	while (!arr.empty() && check) {
		int x = arr.top().x;
		int y = arr.top().y;
		int time = arr.top().time;
		arr.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			int nt = time + 1;
			if (ny < 1 || nx < 1 || ny > bn || nx > bn) continue;
			if (visualmap[ny][nx] != 0) continue;
			visualmap[ny][nx] = nt;
			arr.push({ ny,nx,nt });

			if (!people[ny][nx].empty()) {
				me = { ny,nx,nt };
				check = 0;
				break;
			}
		}
	}
	/*
	for (int i = 1; i <= bn; i++) {
		for (int j = 1; j <= bn; j++) {
			cout << visualmap[i][j] << " ";
		}
		cout << endl;
	}
	*/
	//맵을 전부 돌았지만 손님을 못찾은 경우
	if (check == 1) {
		score = -1;
		return { 0,0,0 };
	}

	//a는 손님이 가야할 도착 예정 지점
	point a = people[me.y][me.x].front();
	people[me.y][me.x].pop_back();

	//연료가 부족한 경우
	if (score < me.time)
		score = -1;

	//연료가 충분한 경우
	else if (score >= me.time)
		score = score - me.time;

	return a;
}

//인자로 받은 도착지점 bfs로 최단경로 탐색
void texi_drive(point arrive) {
	point a = me;
	int visualmap[23][23] = { 0 };
	copy(&map[0][0], &map[0][0] + 23 * 23, &visualmap[0][0]);
	visualmap[me.y][me.x] = -2;

	queue<point>arr;
	arr.push({ a.y,a.x,0 });
	bool check = 1;

	//출발지 == 도착지인 경우
	if (me.y == arrive.y && me.x == arrive.x) {
		check = 0;
		a = { me.y,me.x,0 };
	}
	//bfs
	while (!arr.empty() && check) {
		int x = arr.front().x;
		int y = arr.front().y;
		int time = arr.front().time;
		arr.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nt = time + 1;
			if (ny < 1 || nx < 1 || ny > bn || nx > bn) continue;
			if (visualmap[ny][nx] != 0) continue;
			visualmap[ny][nx] = nt;
			arr.push({ ny,nx,nt });

			if (arrive.x == nx && arrive.y == ny) {
				a = { ny,nx,nt };
				check = 0;
				break;
			}

		}
	}
	//map을 전부 돌았지만 찾지 못한 경우
	if (check == 1) {
		score = -1;
		return;
	}
	//연료가 충분한 경우
	if (score >= a.time) {
		me = { a.y,a.x,0 };
		score = score + a.time;
		return;
	}
	//연료가 부족한 경우
	else if (score < a.time) {
		score = -1;
		return;
	}
}

//사람 명수만큼 for문 돌려서 전부 탐색하거나, 중간에 score = -1를 받아서 택시 운행 중단
void simulation() {
	for (int i = 0; i < bm; i++) {
		point imm = find_people(); //도착지 정보가 담겨있음
		if (score < 0) break;
		texi_drive(imm);
		if (score < 0) break;
	}
	cout << score;
}
int main(void) {
	input();
	simulation();
	return 0;
}

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

문제

문제

출처

ICPC

반례를 찾을 수 없어 도움을 요청드립니다.

wjd5126 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말