1. y시작,x시작,y종료,x종료,현재 택시위치에서의 거리 d 이 5가지를 저장하는 구조체 P를 정의한다. 2. vector<P> s를 정의 M개의 P를 저장한다. 3. M회 루프를 돌면서 매 시행마다 s를 정렬해준다. 정렬은 comparator 를 재정의하는 방식으로 한다. 거리,y좌표,x 우선순위로 정렬하면 항상 s[0]이 지금 태우러 가야하는 사람이다. 뽑은 뒤 s[0]은 필요없으므로 벡터에서 지워준다. 4. 벽에 의해 택시로 도달할 수 없는 사람이 있는 겨우와, 연료를 다쓰는 경우를 예외처리 해준다.
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
struct P{
int y,x,ey,ex,d;
};
vector<P> s;
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
int N,M,K,map[21][21],py,px,INF=9e8;
bool visit[21][21];
int bfs(int y,int x){
memset(visit,0,sizeof(visit));
queue<P> q;
q.push({y,x});
visit[y][x] = 1;
int ret = 0;
while(!q.empty()){
int sz = q.size();
while(sz--){
P qf = q.front(); q.pop();
if(qf.y==py&&qf.x==px) return ret;
for(int i=0;i<4;i++){
int ny = qf.y+dy[i];
int nx = qf.x+dx[i];
if(ny < 1 || nx < 1 || ny > N || nx > N || map[ny][nx]) continue;
if(!visit[ny][nx]){
q.push({ny,nx});
visit[ny][nx] = 1;
}
}
}
ret++;
}
return INF;
}
bool cmp(P& a,P& b){
if(a.d < b.d) return 1;
else if(a.d==b.d){
if(a.y<b.y) return 1;
else if(a.y==b.y) return a.x < b.x;
return 0;
}
return 0;
}
int main(){
scanf("%d%d%d",&N,&M,&K);
s.resize(M);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++) scanf("%d",&map[i][j]);
scanf("%d%d",&py,&px);
for(int i=0;i<M;i++) scanf("%d%d%d%d",&s[i].y,&s[i].x,&s[i].ey,&s[i].ex);
for(int i=0;i<M;i++){
for(int j=0;j<s.size();j++) s[j].d = bfs(s[j].y,s[j].x);
sort(s.begin(),s.end(),cmp);
P t = s[0];
s.erase(s.begin());
if(K-t.d < 0) {
K=-1;
break;
}
K-=t.d, py=t.y, px=t.x;
int nDist = bfs(t.ey,t.ex);
if(K-nDist < 0){
K=-1;
break;
}
py=t.ey, px=t.ex;
K+=nDist;
}
printf("%d",K);
}