글 읽기 - 테스트케이스는 다 맞았는데 제출하자마자 에러가 뜹니다ㅠㅠ

mjy3966 3년 전 0

한번만 봐주세요...

웬만한 반례도 다 만들어 봤는데요 안되네요ㅠ

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

#define MAX 20
using namespace std;


typedef struct
{
	bool obstacle;
	bool person;
}MAP_Info;

typedef struct
{
	int use_oil;
	bool check;
	int start_x;
	int start_y;
	int goal_x;
	int goal_y;

}Passenger_Info;

typedef struct
{
	int x;
	int y;
	int left_oil;
	bool run = true;
	int passenger_num;
}Taxi_Info;

typedef struct
{
	int x, y;
}Dir;


int N, M, oil;
MAP_Info MAP[MAX][MAX];
Passenger_Info Passenger[MAX*MAX];
Taxi_Info Taxi;
vector<pair<int, int>> min_dist;

Dir direct[4] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

void Input()
{
	cin >> N >> M >> Taxi.left_oil;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int a; cin >> a;
			if (a == 1)
			{
				MAP[i][j].obstacle = true;
			}
		}
	}
	int a, b;
	cin >> a  >> b;
	Taxi.x = a - 1;
	Taxi.y = b - 1;

	for (int i = 0; i < M; i++)
	{
		int sx, sy, gx, gy;
		cin >> sx >> sy >> gx >> gy;
		Passenger[i].start_x = sx-1;
		Passenger[i].start_y = sy-1;
		Passenger[i].goal_x = gx-1;
		Passenger[i].goal_y = gy-1;
		MAP[sx][sy].person = true;
	}
}

int BFS(int gx, int gy)
{
	int sx = Taxi.x;
	int sy = Taxi.y;
	//int gx = Passenger[num].start_x;
	//int gy = Passenger[num].start_y;
	
	queue<pair<int, int>> q;
	int map[MAX][MAX] = { 0, };
	//map[sx][sy] = 400;
	q.push({ sx, sy });
	int dist = 999;
	while (!q.empty())
	{
		pair<int, int> cur;
		cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cur.first + direct[i].x;
			int ny = cur.second + direct[i].y;

			if ((nx == sx && ny == sy) ||nx < 0 || ny < 0 || nx >= N || ny >= N || MAP[nx][ny].obstacle == true) continue;
			if (nx >= 0 && nx < N && ny >= 0 && ny < N && !MAP[nx][ny].obstacle)
			{
				
				if (map[nx][ny] == 0 || map[nx][ny] > map[cur.first][cur.second] + 1)
				{
					map[nx][ny] = map[cur.first][cur.second] + 1;
					q.push({ nx, ny });
				}
				if (nx == gx && ny == gy)
				{
					int d = map[nx][ny];
					if (d < dist) dist = d;
					break;
				}
				

			}
			

		}

		
	}
	if (map[gx][gy] == 0)
	{
		Taxi.run = false;
	}
	return dist;

}

int Calc_dist()
{
	int d = 9999;
	int passenger_num;
	
	for (int i = 0; i < M; i++)
	{
		if (Passenger[i].check == true) continue;
		int gx = Passenger[i].start_x;
		int gy = Passenger[i].start_y;
		int result;
		if (gx == Taxi.x && gy == Taxi.y)			//태우러 가는 승객이 출발지점일때
		{
			result = 0;
			
		}
		else result = BFS(gx, gy);			//승객 태우러 가는 거리
		if (result <= d)
		{
			if (result == d)
			{
				int n = Taxi.passenger_num;
				if (gx > Passenger[n].start_x)
					continue;
				else if (gx == Passenger[n].start_x)
				{
					if (gy > Passenger[n].start_y)
						continue;
				}
			}
			passenger_num = i;
			d = result;
			Taxi.passenger_num = i;
		}
	}
	if (Taxi.left_oil - d > 0)
	{
		Taxi.left_oil -= d;
	}
	else
	{
		Taxi.run = false;
	}
	return passenger_num;
}
void Solution()
{
	int a = M;
	while (a--)
	{
		int num = Calc_dist();  //태울 승객 번호
		if (Taxi.run == false)
		{
			cout << -1 << endl;
			return;
		}
		Taxi.x = Passenger[num].start_x;
		Taxi.y = Passenger[num].start_y;
		int gx = Passenger[num].goal_x;
		int gy = Passenger[num].goal_y;
		if (Taxi.x == gx && Taxi.y == gy) continue;
		
		int dist = BFS(gx, gy);			// 승객 목적지까지 거리

		if (Taxi.left_oil - dist >= 0)
		{
			Taxi.left_oil += dist;
			Passenger[num].check = true;
			Taxi.x = gx;
			Taxi.y = gy;

		}
		else
		{
			Taxi.run == false;
			cout << -1 << endl;
			return;
		}


	}

	cout << Taxi.left_oil << endl;
}

int main()
{
	Input();
	Solution();
}

alsdk3586 3년 전 1

저도 그랬는데

1. 동일한 거리인 사람이 많을 경우, 행/렬로 우선순위 결정

2. 사람이 서있어도 택시는 거기를 지나갈 수 있다. (이거 찾는데 오래걸렸어요..ㅠㅠ 저는 map에 바로 사람이 서잇는 곳을 표시해줫거든요. 그래서 사람이 서있는 곳을 통과해서 가는 경로를 탐색하지 못했어요)

3. 출발지와 도착지가 동일한 경우

4. 택시와 출발지가 동일한 경우

이렇게 4가지의 경우를 확인해보시겠어요? 저는 이렇게 해서 일단 초반 틀렸습니다는 해결했습니다!

dhtlrhf96 2년 전 0

와 2번 사항때문에 30분동안 해맸네요... 지나갈 수 없는줄 알고 예외처리 까지 해가며 만들었는데 이 댓글보고 지우니까 해결됐습니다.

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

문제

문제

출처

ICPC

테스트케이스는 다 맞았는데 제출하자마자 에러가 뜹니다ㅠㅠ

mjy3966 3년 전 0

alsdk3586 3년 전 1

dhtlrhf96 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말