#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
#define MAX_WIDTH 20
#define MAX_CUSTOMER 400
#define CUSTOMER 123
using namespace std;
typedef struct Taxi {
int row;
int col;
int fuel;
} Taxi;
typedef struct Customer {
int currentRow;
int currentCol;
int dstRow;
int dstCol;
int distance;
} Customer;
typedef struct Candidate {
int row;
int col;
int fuel;
int index;
bool operator < (Candidate t) {
if (fuel < t.fuel)
return true;
else if (fuel > t.fuel)
return false;
else {
if (row < t.row)
return true;
else if (row > t.row)
return false;
else {
if (col < t.col)
return true;
else
return false;
}
}
}
} Candidate;
int map[MAX_WIDTH][MAX_WIDTH];
int width, numOfCustomer;
Taxi taxi;
Customer customer[MAX_CUSTOMER];
//nxn ํฌ๊ธฐ ๋งต์ ๊ฐ ์นธ์ ๋ฒฝ ๋๋ ๋น์นธ
//๋น์นธ์ ์น๊ฐ๊ณผ ํ์๊ฐ ์ฌ ์ ์์
//m ๋ช
์ ํ์์ผํ๊ณ , m๋ช
์ ๊ฐ๊ฐ ํฉ์ด์ ธ ์์
//ํ์ฌ ํ์์์น์์ ๊ฐ์ฅ ๊ฐ๊น์ด ์น๊ฐ์ ํ์ฐ๊ณ , ์ฌ๋ฌ๋ช
์ด๋ฉด ํ์ด ์๊ณ , ์ด์ด ์์ ์น๊ฐ ๋จผ์
//ํ์์ ์น๊ฐ์ด ๊ฐ์ ์์น๋ฉด 0, ์น๊ฐ์ ์ฑ๊ณต์ ์ผ๋ก ํ์๋ค์ฃผ๋ฉด, ํ์๋ค์ฃผ๋๋ผ ์๋ชจํ ์ฐ๋ฃ์ ๋๋ฐฐ๊ฐ ์ถฉ์ ๋จ.
//ํ์ฐ๋ ๋์ค์ ์ฐ๋ฃ๊ฐ ์์ง๋๋ฉด ๊ทธ๊ฑธ๋ก ์
๋ฌด ์ข
๋ฃ. ๋์ฐฉ๊ณผ ๋์์ ์์ง์ ๊ด์ฐฎ๋ค.
//์น๊ฐ์ ํ์ฐ๋ฌ ๊ฐ๋ ๋์ค์๋ ์ฐ๋ฃ๋ ์๋ชจ๋๋ค.
int startWork();
void getCustomerDistance();
bool check();
int main() {
cin >> width >> numOfCustomer >> taxi.fuel;
for (int i = 0; i < width; i++) {
for (int j = 0; j < width; j++)
cin >> map[i][j];
}
cin >> taxi.row >> taxi.col;
taxi.row--;
taxi.col--;
for (int i = 0; i < numOfCustomer; i++) {
cin >> customer[i].currentRow >> customer[i].currentCol >> customer[i].dstRow >> customer[i].dstCol;
customer[i].currentRow--;
customer[i].currentCol--;
customer[i].dstRow--;
customer[i].dstCol--;
customer[i].distance = -1;
map[customer[i].currentRow][customer[i].currentCol] = CUSTOMER + i;
}
getCustomerDistance();
if (check())
cout << startWork();
else
cout << -1;
}
void getCustomerDistance() {
for (int i = 0; i < numOfCustomer; i++) {
bool visit[MAX_WIDTH][MAX_WIDTH] = { 0, };
list<Taxi> q;
vector<int> candidate;
q.push_back({ customer[i].currentRow, customer[i].currentCol, 0 });
visit[customer[i].currentRow][customer[i].currentCol] = true;
while (!q.empty()) {
Taxi temp = q.front();
q.pop_front();
if (temp.row == customer[i].dstRow && temp.col == customer[i].dstCol) {
customer[i].distance = temp.fuel;
break;
}
if (temp.row != 0 && map[temp.row - 1][temp.col] != 1 && !visit[temp.row - 1][temp.col]) {
q.push_back({ temp.row - 1, temp.col, temp.fuel + 1 });
visit[temp.row - 1][temp.col] = true;
}
if (temp.row != width - 1 && map[temp.row + 1][temp.col] != 1 && !visit[temp.row + 1][temp.col]) {
q.push_back({ temp.row + 1, temp.col, temp.fuel + 1 });
visit[temp.row + 1][temp.col] = true;
}
if (temp.col != 0 && map[temp.row][temp.col - 1] != 1 && !visit[temp.row][temp.col - 1]) {
q.push_back({ temp.row, temp.col - 1, temp.fuel + 1 });
visit[temp.row][temp.col - 1] = true;
}
if (temp.col != width - 1 && map[temp.row][temp.col + 1] != 1 && !visit[temp.row][temp.col + 1]) {
q.push_back({ temp.row, temp.col + 1, temp.fuel + 1 });
visit[temp.row][temp.col + 1] = true;
}
}
}
}
bool check() {
for (int i = 0; i < numOfCustomer; i++)
if (customer[i].distance == -1)
return false;
return true;
}
int startWork() {
for (int i = 0; i < numOfCustomer; i++) {
//๊ฐ์ฅ ๊ฐ๊น์ด ์น๊ฐ ๋ฝ์์ ๋ฐ ๋ณ์์ ์ ์ฅ.
Customer crtCustomer;
int crtCustomerDistance = 0;
if (map[taxi.row][taxi.col] >= CUSTOMER)
crtCustomer = customer[map[taxi.row][taxi.col] - CUSTOMER];
else {
bool visit[MAX_WIDTH][MAX_WIDTH] = { 0, };
visit[taxi.row][taxi.col] = true;
list<Taxi> q;
q.push_back({ taxi.row, taxi.col, 0 });
vector<Candidate> candidate;
while (!q.empty()) {
Taxi temp = q.front();
q.pop_front();
if(map[temp.row][temp.col] >= CUSTOMER)
candidate.push_back({ temp.row , temp.col, temp.fuel, map[temp.row][temp.col] - CUSTOMER });
if (temp.row != 0 && map[temp.row - 1][temp.col] != 1 && !visit[temp.row - 1][temp.col]) {
q.push_back({ temp.row - 1, temp.col, temp.fuel + 1 });
visit[temp.row - 1][temp.col] = true;
}
if (temp.row != width - 1 && map[temp.row + 1][temp.col] != 1 && !visit[temp.row + 1][temp.col]) {
q.push_back({ temp.row + 1, temp.col, temp.fuel + 1 });
visit[temp.row + 1][temp.col] = true;
}
if (temp.col != 0 && map[temp.row][temp.col - 1] != 1 && !visit[temp.row][temp.col - 1]) {
q.push_back({ temp.row, temp.col - 1, temp.fuel + 1 });
visit[temp.row][temp.col - 1] = true;
}
if (temp.col != width - 1 && map[temp.row][temp.col + 1] != 1 && !visit[temp.row][temp.col + 1]) {
q.push_back({ temp.row, temp.col + 1, temp.fuel + 1 });
visit[temp.row][temp.col + 1] = true;
}
}
if (candidate.size() == 0)
return -1;
sort(candidate.begin(), candidate.end());
crtCustomer = customer[candidate[0].index];
crtCustomerDistance = candidate[0].fuel;
}
//๊ฐ์ฅ ๊ฐ๊น์ด ์น๊ฐ์ ๋ฐ๋ฆฌ๊ณ , ์ฐ๋ฃ ์ถฉ๋ถํ์ง, ์ถฉ๋ถํ๋ฉด ์ด๋์ํด
map[crtCustomer.currentRow][crtCustomer.currentCol] = 0;
int distance = crtCustomer.distance + crtCustomerDistance;
if (distance <= taxi.fuel) {
taxi.row = crtCustomer.dstRow;
taxi.col = crtCustomer.dstCol;
taxi.fuel -= distance;
taxi.fuel += (2*crtCustomer.distance);
}
else
return -1;
}
return taxi.fuel;
}