스타트 택시 C++

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

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

using namespace std;

const int MAX = 21;
int map[MAX][MAX];
int oil,n,m;
pair<int, int> loc;
struct texi { int ci, cj, mi, mj; };
vector <texi> pg;
struct MOVE { int x, y; };
MOVE mv[4] = { {-1,0}, {0,-1}, {0,1}, {1,0} };
int visited[MAX][MAX];

int bfs(int i, int j, int index) {
	memset(visited, -1, sizeof(visited));
	int answer = 0;
	queue <pair<pair<int, int>,int>> q;

	q.push(make_pair(make_pair(i, j),0));

	while (!q.empty()) {
		pair<pair <int, int>,int> temp = q.front();
		q.pop();
		int count = temp.second;

		for (int k = 0; k < 4; k++) {
			int movei = temp.first.first + mv[k].x;
			int movej = temp.first.second + mv[k].y;

			if (movei == pg[index].ci && movej == pg[index].cj) {
				return count+1;
			}

			if (movei > 0 && movei <= n && movej > 0 && movej <= n) {
				if (map[movei][movej] == 0 && visited[movei][movej] == -1) {
					visited[movei][movej] = 1;
					q.push(make_pair(make_pair(movei, movej),count+1));
				}
			}
		}
	}
	return 987654321;
}

pair<int, int> FindShortest() {
	pair<int, int> answer = make_pair(-1, 987654321);

	for (int i = 0; i < pg.size(); i++) {
		int temp;
		if (pg[i].ci == loc.first && pg[i].cj == loc.second)
			temp = 0;
		else
			temp = bfs(loc.first, loc.second,i);
		if (temp < answer.second) {
			answer = make_pair(i, temp);
		}
		else if (temp == answer.second) {
			if (pg[i].ci < pg[answer.first].ci) {
				answer = make_pair(i, temp);
			}
			else if (pg[i].ci == pg[answer.first].ci) {
				if (pg[i].cj < pg[answer.first].cj)
					answer = make_pair(i, temp);
			}
		}
	}
	return answer;
}

int bfs2(int i, int j, int index) {
	memset(visited, -1, sizeof(visited));
	int answer = 0;
	queue <pair<pair<int, int>, int>> q;

	q.push(make_pair(make_pair(i, j), 0));

	while (!q.empty()) {
		pair<pair <int, int>, int> temp = q.front();
		q.pop();
		int count = temp.second;

		for (int k = 0; k < 4; k++) {
			int movei = temp.first.first + mv[k].x;
			int movej = temp.first.second + mv[k].y;

			if (movei == pg[index].mi && movej == pg[index].mj) {
				return count+1;
			}

			if (movei > 0 && movei <= n && movej > 0 && movej <= n) {
				if (map[movei][movej] == 0 && visited[movei][movej] == -1) {
					visited[movei][movej] = 1;
					q.push(make_pair(make_pair(movei, movej), count + 1));
				}
			}
		}
	}
	return -1;
}

int MovePassenger(int index) {
	int need_oil;
	if (loc.first == pg[index].mi && loc.second == pg[index].mj)
		need_oil = 0;
	else
		need_oil = bfs2(loc.first, loc.second, index);
	
	return need_oil;
}

int main(void) {
	cin >> n >> m >> oil;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}

	int i, j;
	cin >> i >> j;
	loc = make_pair(i, j);

	for (int i = 0; i < m; i++) {
		int currenti, currentj, movei, movej;
		cin >> currenti >> currentj >> movei >> movej;
		pg.push_back({ currenti,currentj,movei,movej });
	}

	while (pg.size() > 0 && oil >0) {
		pair<int,int> temp = FindShortest();
		//어느 승객한테도 갈 수 없는 경우
		if (temp.second == 987654321)	break;
		//오일 값 제거
		if (oil - temp.second <= 0)	break;
		oil = oil - temp.second;
		loc = make_pair(pg[temp.first].ci, pg[temp.first].cj);
		int use_oil = MovePassenger(temp.first);
		//승객을 목적지로 이동시킬 수 없는 경우
		if (use_oil == -1)	break;
		//오일 값 제거 + 충전
		if (oil < use_oil)	break;
		else
			oil = oil + use_oil;
		loc = make_pair(pg[temp.first].mi, pg[temp.first].mj);
		pg.erase(pg.begin() + temp.first);
	}
	if (pg.size() == 0)
		cout << oil << endl;
	else
		cout << -1 << endl;
}