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

質問する

尚根は刑務所で2人の囚人を脱獄する.この刑務所は1階建てで、尚根は平面図を手に入れたばかりだ.
平面図にはすべての壁とドアが表示され、脱獄が必要な囚人の位置も表示されています.刑務所は無人の刑務所で、2人の囚人だけが刑務所にいる.
ドアは中央制御室でしか開けられません.尚根は特別な技術で制御室を通らずにドアを開けようとした.しかし、ドアを開けるのに時間がかかります.2人の囚人が脱獄したときに開くドアの数を求めるプログラムを書く.ドアを開けるとずっと開いている.

入力

最初の行は、テスト例の数を示します.テストボックスの数は100個を超えない.
第1行は、平面図の高さhと幅wを与える.(2≦h,w≦100)次のh行は刑務所の平面図情報を提供し,スペースは「.」である.通れない壁は「*」、ドアは「#」、囚人の位置は「$」.
尚勤は刑務所の外を自由に移動することができ、平面図に示されている囚人の数はいつも2人である.各囚人と刑務所の外の接続経路が常に存在する場合にのみ入力される.

しゅつりょく

各テストボックスは、2人の囚人が脱獄するために開かなければならないドアの最高値を出力します.

サンプルI/O

入力

例1

3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********

例出力1

4
0
9

Solution

#include <iostream>
#include <vector>
#include <queue>
#define MAX 102
#define INF 987654

using namespace std;

int N, M;
char MATRIX[MAX][MAX];
int Dist[3][MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1 ,0 ,0};
vector<pair<int, int>> prisoner;

void init(){
	prisoner.clear();
	for(int i = 0; i < MAX; i++){
		fill_n(MATRIX[i], MAX, '.');
	}
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < MAX; j++){
			fill_n(Dist[i][j], MAX, INF);
		}
	}
}

void Dijkstra(int X, int Y, int Pos){
	priority_queue<pair<int, pair<int, int>>> PQ;
	PQ.push({0, {X, Y}});
	Dist[Pos][X][Y] = 0;
	while (!PQ.empty()){
		int x = PQ.top().second.first;
		int y = PQ.top().second.second;
		int cost = -PQ.top().first;
		PQ.pop();
		if(Dist[Pos][x][y] < cost) continue;
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			int curCost = cost;
			if(nx >= 0 && nx <= N+1 && ny >= 0 && ny <= M+1 && MATRIX[nx][ny] != '*'){
				if(MATRIX[nx][ny] == '#') curCost++;
				if(Dist[Pos][nx][ny] > curCost){
					PQ.push({-curCost, {nx, ny}});
					Dist[Pos][nx][ny] = curCost;
				}
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T; cin >> T;
	while(T--){
		init();
		cin >> N >> M;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++) {
				cin >> MATRIX[i][j];
				if(MATRIX[i][j] == '$') prisoner.push_back({i, j});
			}
		}
		Dijkstra(0, 0, 0);
		Dijkstra(prisoner[0].first, prisoner[0].second, 1);
		Dijkstra(prisoner[1].first, prisoner[1].second, 2);		
		int minimum = 99999;
		int cost = 99999;
		for(int i = 0; i <= N+1; ++i){
			for(int j = 0; j <= N+1; ++j){
				if(MATRIX[i][j] != '*'){
					cost = Dist[0][i][j] + Dist[1][i][j] + Dist[2][i][j];
					if(MATRIX[i][j] == '#') cost -= 2;
					minimum = min(minimum, cost);
				}
			}
		}
		cout << minimum << '\n';
	}
}

難しいですね.多益アルゴリズムが解決できる問題ではないことを知っている.
まず観点を固めなければならない.
1.刑務所の囚人2人
2.二人を逃がすために存在する一人
この3人を基準に、ドエストラアルゴリズムを回せばいい.
主な考え方は以下の通りです.現在のデータを受信すると、1~N~1~Mの間のデータが受信される.しかし、刑務所全体の果てに別の空間があるとしたら?

刑務所の境界のほかにもう一つの空間があり、0, 0の位置で、尚根がドアを開ける立場であれば、この考えは重要です.

void init(){
	prisoner.clear();
	for(int i = 0; i < MAX; i++){
		fill_n(MATRIX[i], MAX, '.');
	}
	for(int i = 0; i < 3; i++){
		for(int j = 0; j < MAX; j++){
			fill_n(Dist[i][j], MAX, INF);
		}
	}
}

したがって、MATRIXのデータは、最初に初期設定では.として全て処理される.面倒なことが二度と起こらないように.

int N, M;
char MATRIX[MAX][MAX];
int Dist[3][MAX][MAX];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1 ,0 ,0};
vector<pair<int, int>> prisoner;

void Dijkstra(int X, int Y, int Pos){
	priority_queue<pair<int, pair<int, int>>> PQ;
	PQ.push({0, {X, Y}});
	Dist[Pos][X][Y] = 0;
	while (!PQ.empty()){
		int x = PQ.top().second.first;
		int y = PQ.top().second.second;
		int cost = -PQ.top().first;
		PQ.pop();
		if(Dist[Pos][x][y] < cost) continue;
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			int curCost = cost;
			if(nx >= 0 && nx <= N+1 && ny >= 0 && ny <= M+1 && MATRIX[nx][ny] != '*'){
				if(MATRIX[nx][ny] == '#') curCost++;
				if(Dist[Pos][nx][ny] > curCost){
					PQ.push({-curCost, {nx, ny}});
					Dist[Pos][nx][ny] = curCost;
				}
			}
		}
	}
}

2 D配列データに複数の項目を書き込むのと同じです.ここでCostは開門料になります最初のCostはまだ開いていませんが、0から始まります.
一人一人が個別にDistデータを処理する.現在の位置で費用を処理する場合、ドアに遭遇したら追加料金を徴収します.

しかし、特定の位置の複数の方向にドアがある場合もある.このため、for文で4方向を処理する場合、コストデータは独立変数として処理します.△筆者はこの部分でずっとミスをしています.
0,0に上根が開いていれば,他の囚人一人一人が自ら開き,この3つの場合についてそれぞれDist配列を求める.この3つのシナリオでデータを比較すればよい.

int minimum = 99999;
int cost = 99999;
for(int i = 0; i <= N+1; ++i){
	for(int j = 0; j <= N+1; ++j){
		if(MATRIX[i][j] != '*'){
			cost = Dist[0][i][j] + Dist[1][i][j] + Dist[2][i][j];
			if(MATRIX[i][j] == '#') cost -= 2;
			minimum = min(minimum, cost);
		}
	}
}
cout << minimum << '\n';

すべての可能な座標を検索し、壁でない場合、Distデータの値が更新され、3つの場合のDist値が更新されます.壁にぶつかったら-2いずれの場合も対応する位置でcost+1を行い,一つの場合に処理した.
やっぱりプラチナ問題は難しい非常に悩んでも多くの助けを得た問題だ.記憶を刻印するために記録する.