[BOJ]19238発タクシー

19238発タクシー

難易度:金貨3
タイプ:BFS、シミュレーション
https://www.acmicpc.net/problem/19238

質問する

StartLinkは「StartTaxi」というタクシー事業を開始した.タクシーを起動するのは特別で、お客さんを目的地に送るたびに燃料が充電され、燃料が切れた当日の仕事は終わります.
タクシー運転手の崔伯俊さんは今日、M人の乗客を乗せることを目標にしています.白俊が活動する分野はNだ.×Nサイズのメッシュで表すことができ、各セルが空または壁になっています.タクシーが空席の場合、上下左右に隣接する空席の一つに移動できます.アルゴリズム経験豊富なBaek Junは,特定の位置に移動すると常に最短経路に移動する.
M人の乗客は1つのスペースに立って、別のスペースの1つに移動する準備をしています.複数の乗客が一緒に搭乗する場合はありません.そのため、白俊は乗客1人を乗せて目的地に向かうM回を繰り返した.乗客一人一人が動かず、出発地でタクシーに乗るしかなく、目的地の地下タクシーに乗るしかありません.
白俊が乗る乗客を選ぶ時、現在の位置で最も短い距離の乗客を選ぶ.このような乗客が多い場合は、その中で一番小さい番号の乗客を選び、そのような乗客が多い場合は、その中で一番小さい番号の乗客を選びます.タクシーと乗客が同じ位置に立っている場合、その乗客までの最短距離はゼロです.燃料は1コマ移動するごとに消費される.1人の乗客を目的地に移動することに成功すると、その乗客が移動中に消費する燃料量は2倍に増加する.移動途中で燃料が切れて移動が失敗し、当日の作業が終了します.乗客を目的地に移すと同時に、燃料が尽きた場合は失敗しない.

＜図1＞
<図1>タクシーが活動するエリアを示す地図で、タクシーと3人の乗客の出発地と目的地を示す.タクシーの現在の燃料量は15です.現在、タクシーから乗客1人あたりの最短距離は9、6、7なので、タクシーは2番の乗客の出発地に向かいます.

＜図2＞

<図3>
<図2>タクシーから2番乗客の出発地までの経路を示し、<図3>2番乗客の出発地から目的地までの経路を示す.目的地に移動する前に消費される燃料は6であり、移動後に12を充電するので、残りの燃料量は15である.現在、タクシーから乗客1人あたりの最短距離は7つなので、タクシーは2つの中でもっと小さい1番の乗客の出発地に移動します.

<図4>

<図5>
<図4>及び<図5>は、タクシー1号の乗客が目的地へ向かう経路を示す.余剰燃料量15-7-7+7×2=15.

＜図6＞

＜図7＞
<図6>および<図7>は、タクシー3号の乗客が目的地に向かう経路を示す.最終残存燃料量15-5-4+4+4×2=14.
すべての乗客を正常に送ることができるかどうかを見つけて、送ることができるならば、プログラムを書いて最終的な余剰燃料の量を出力してください.

入力

第1列は、N、Mおよび初期燃料の量を与える.(2≦N≦20,1≦M≦N 2,1≦初期燃料≦500000)燃料は無限に充填できるので、初期燃料の量を超えて満タンになる可能性がある.
次の行から、N行において、伯俊活動領域の地図が与えられる.0はスペース、1は壁です.
次の行は白俊が運転を始めた車両の行番号と列番号を示した.行と列番号は1以上N以下の自然数で、運転を開始したのはスペースです.
次の行から、各乗客の出発地の行と列番号、および目的地の行と列番号.すべての出発地と目的地は空いていて、出発地ごとに異なり、お客様の出発地と目的地ごとに異なります.

しゅつりょく

すべてのお客様を動員し、燃料が満たされたときに残りの燃料の量を出力します.しかし、移動途中で燃料が尽き、次の出発地または目的地に移動できない場合は、−1が出力される.すべてのお客様を移動できなくても、-1を出力します.

に答える

これはBFS利用の問題です.
出発点から一番近いところへ残りの乗客を迎えに行きます.
逆に、同じ距離の乗客がいれば、乗客の位置基準の行番号が小さい人が優先し、行番号が同じであれば、列番号が小さい人が優先する.
もちろん、出発点から乗客を迎えに行き、燃料が切れたら運転終了-1出力
お客様を乗せて目的地に到着するまで燃料が切れたら運転停止-1出力
目的地まで送ることに成功すれば、あなたを乗せた場所から目的地までの距離の2倍の燃料充電になります.
すべてのお客様を目的地に乗せたら、残りの燃料出力量は
実施自体は少しも難しくないと思います...始まりました.

コード#コード#

package DFS와BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * BOJ_19238_G3_스타트 택시
 * @author mingggkeee
 * BFS, 시뮬레이션
 */

public class BOJ_19238 {
	
	static class Location{
		int r;
		int c;
		int count;
		
		public Location(int r, int c, int count) {
			this.r = r;
			this.c = c;
			this.count = count;
		}
		
	}
	
	static int N, M, fuel;
	static int[][] map, people, destination;
	static int startR, startC;
	static boolean[][] isVisited;
	static int minDistance;
	static boolean[] visited;
	static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		fuel = Integer.parseInt(st.nextToken());
		
		map = new int[N+1][N+1];
		people = new int[M][2];
		destination = new int[M][2];
		visited = new boolean[M];
		
		for(int r=1; r<=N; r++) {
			st = new StringTokenizer(br.readLine());
			for(int c=1; c<=N; c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		
		st = new StringTokenizer(br.readLine());
		startR = Integer.parseInt(st.nextToken());
		startC = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			people[i][0] = Integer.parseInt(st.nextToken());
			people[i][1] = Integer.parseInt(st.nextToken());
			
			destination[i][0] = Integer.parseInt(st.nextToken());
			destination[i][1] = Integer.parseInt(st.nextToken());
		}
		
		while(fuel != 0) {
			minDistance = Integer.MAX_VALUE;
			int idx = -1;
			int cnt = 0;
	
			
			for(int i=0; i<M; i++) {
				if(visited[i]) {
					cnt++;
					continue;
				}
				int compare = bfs(startR, startC, people[i][0], people[i][1]);
				if(compare < minDistance && compare > -1) {
					idx = i;
					minDistance = compare;
				}
				else if(compare == minDistance) {
					
					if(people[i][0] < people[idx][0]) {
						idx = i;
					}
					else if(people[i][0] == people[idx][0] && people[i][1] < people[idx][1]) {
						idx = i;
					}
					
				}
			}
			
			if(cnt == M) {
				break;
			}
			
			if(idx == -1) {
				fuel = -1;
				break;
			}
			
			fuel -= minDistance;
			startR = people[idx][0];
			startC = people[idx][1];
			
			
			minDistance = bfs(startR, startC, destination[idx][0], destination[idx][1]);
			
			if(minDistance == -1) {
				fuel = -1;
				break;
			}
			
			fuel += minDistance;
			visited[idx] = true;
			startR = destination[idx][0];
			startC = destination[idx][1];
		
			
		}
		
		System.out.println(fuel);
		
		
	}
	
	static int bfs(int startR, int startC, int endR, int endC) {
		
		isVisited = new boolean[N+1][N+1];
		isVisited[startR][startC] = true;
		
		Queue<Location> queue = new LinkedList<>();
		queue.offer(new Location(startR, startC, 0));
		
		while(!queue.isEmpty()) {
			Location now = queue.poll();
			
			if(fuel < now.count) {
				return -1;
			}
			
			if(now.r==endR && now.c==endC) {
				return now.count;
			}
			
			for(int i=0; i<4; i++) {
				int nr = now.r + dir[i][0];
				int nc = now.c + dir[i][1];
				
				if(nr>=1 && nc>=1 && nr<=N && nc<=N && !isVisited[nr][nc] && map[nr][nc] != 1) {
					isVisited[nr][nc] = true;
					queue.offer(new Location(nr, nc, now.count+1));
				}
			}
			
		}
		
		return -1;
		
	}

}