백준 19238번 : 스타트 택시 (c++)

www.acmicpc.net/problem/19238

19238번: 스타트 택시

문제
스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

입력
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력
모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

확인사항
출발지끼리만 다르고 목적지끼리만 다른 것 다른 승객들끼리 출발지랑 목적지랑 겹칠 수 있다.

예제 입력 1 
6 3 15
0 0 1 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
6 5
2 2 5 6
5 4 1 6
4 2 3 5
예제 출력 1 
14

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

using namespace std;


struct taxi {
	int sy, sx, ey, ex;
	bool chk;
};
int arr[21][21];
taxi taxis[401];
int Distance[21][21];
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
int N, M, G;
int y, x;

void bfs(int yy, int xx) {
	memset(Distance, -1, sizeof(Distance));
	queue <pair<int, int>> q;
	Distance[yy][xx] = 0;
	q.push({ yy,xx });

	while (!q.empty()) {
		yy = q.front().first;
		xx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = yy + dy[i];
			int nx = xx + dx[i];
			if (ny < 1 || nx < 1 || ny > N || nx > N)	continue;
			if (arr[ny][nx] == -1)	continue;
			if (Distance[ny][nx] != -1) continue;
			Distance[ny][nx] = Distance[yy][xx] + 1;
			q.push({ ny,nx });
		}
	}
}

void simulation() {
	
	for(int i=0;i<M;i++){
		//제일 가까운 곳 찾기
		bfs(y, x);
		int tempdistance = 98787987;
		int cy = 0;
		int cx = 0;
		int find = 0;
		for (int i = 1; i <= M; i++)
		{
			if (taxis[i].chk) continue;
			if (Distance[taxis[i].sy][taxis[i].sx] < tempdistance) {
				cy = taxis[i].sy;
				cx = taxis[i].sx;
				tempdistance= Distance[taxis[i].sy][taxis[i].sx];
				find = i;
			}
			if (Distance[taxis[i].sy][taxis[i].sx] == tempdistance) {
				if (cy > taxis[i].sy) {
					cy = taxis[i].sy;
					cx = taxis[i].sx;
					find = i;
				}
				else if (cy == taxis[i].sy) {
					if (cx > taxis[i].sx) {
						cy = taxis[i].sy;
						cx = taxis[i].sx;
						find = i;
					}
				}
			}
		}
		y = cy;
		x = cx;
		taxis[find].chk = true;
		//연료확인
		if (Distance[cy][cx] == -1) {
			G = -1;
			return;
		}
		G -= Distance[cy][cx];
		if (G < 0) {
			G = -1;
			return;
		}
		//목적지 찾기
		bfs(y, x);
		y = taxis[find].ey;
		x = taxis[find].ex;
		if (Distance[taxis[find].ey][taxis[find].ex]==-1) {
			G = -1;
			return;
		}
		//연료 확인
		G -= Distance[taxis[find].ey][taxis[find].ex];
		if (G < 0) {
			G = -1;
			return;
		}
		G += 2 * Distance[taxis[find].ey][taxis[find].ex];
	}

}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> N >> M >> G;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 1) {
				arr[i][j] = -1;
			}
		}
	}
	cin >> y >> x;

	for (int i = 1; i <= M; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		taxis[i] = { a,b,c,d,false};
	}

	simulation();
	cout << G;
	return 0;
}