「レスキュー、ZOJ 1649」の解法と疑問
4239 ワード
1.1タイトル番号:ZOJ 1649
詳細:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1649
1.2テーマ説明:
AngelはMOLIGPYに捕まって刑務所に閉じ込められた.刑務所はNを1つ使うことができます×Mのマトリックスで説明すると、1
Angelの友達はAngelを救いに行きたいと思っています.彼の任務はAngelに近づくことだ.「Angelに近づく」という約束は、Angelが閉じ込められた位置に着くことを意味します.Angelの友达がある四角い格子を考えているが、四角い格子の中に警備員がいるなら、警備員を殺さなければ、この四角い格子に着くことができない.Angelの友人が上,下,左,右へ一歩移動するのに1単位時間,警備員を殺すのに1単位時間とする.Angelの友达がこんなに強くて、すべての警備員を殺すことができると仮定します.あなたの任務はAngelの友达がAngelに近づくのに少なくともどのくらいの時間がかかるかを計算することです.上、下、左、右にしか移動できません.壁は通過できません.
1.3入力説明
入力ファイルに複数のテストデータが含まれています.各テストデータの第1の動作は2つの整数NとMであり、次はN行であり、各行はM文字である:"."道路を表し、「a」はAngelを表し、「r」はAngelの友人を表し、「#」は壁を表し、「x」は警備員を表す(各テストデータには「a」と「r」の文字が1つしかないことに注意).ファイルの最後までデータを入力します.
1.4出力説明
入力ファイルのテストデータごとに、Angelに近い最小時間を示す整数を出力します.Angelに近づけない場合は、「PoorANGEL has to stay in the prison all his life.」と出力します.
二、考え方
問題の要求は,rから出発して,aまでの所要時間が最も短い経路を見つけ,最短時間を出力することである.
0.複数の経路が存在する可能性がある(また、ガードによる影響を考慮すると、ステップ数が最も少ない経路は必ずしも時間が最も短い経路ではない)ため、まず広さ優先アルゴリズムの採用が考えられる.2 D配列を使用して、ポイントに到達する最小時間を記録します.これにより、Angelを救出する最小時間を見つけることができます.
1.警備員については、その時点に到達するまでの時間が通常点よりも多くなるように簡単に処理することができる1
2.本題は比較的典型的な広さ優先アルゴリズムBFSで実現できる--Queueを確立し、次の点を順番に列挙し、新しい要求に合致する点を列挙する.QueueはC++が提供するタイプを直接使用することができますが、何を列挙するかは私たちに確定させます.ここでは,x,y,timeの3つの要素を含むNode構造体を構築し,前者は座標を示し,後者はその点に到達するのに要する時間を示す.
3.したがって、全体的な考え方は、r点から4方向に探索し、その点に到達した時間が、元の記録された到達点よりも短ければ、その点から新しい探索を継続する(この点を列に入れる)ことである.キュー内の点が全て探索された後、a点が最小時間(初期設定の最大値ではない)に対応すれば、Angelを救出することができる.
特筆すべきは、本題には大きな穴があることだ.
刑務所はNを1つ使うことができます×Mのマトリクスで説明すると、1」ですが、ZOJはテスト用例では200以上のデータを使っているはずなので、MAXを200にするとZOJでテストするときに「Wrong Answer」と報告して202に変更しなければOKではありません
これからZOJの問題をするにも配列境界を緩和すべきだ.
三、解答
完全なプログラムは以下の通りで、ZOJのテストに合格することができます.
四、疑問
この問題はすでに解けたが,まだ多くの疑問が残っているので,達人に知らせてもらいたい.
1.深さ優先アルゴリズムでこの問題を解くことができますか?理由は?
2.INTを使おうとしたMAX(#include)はLGMN(#define LGNM 1000000)の代わりに使われていますが、いったん置き換えると正確な結果が得られません.これはなぜですか?
3.BFS最後のif文についての質問
バージョン1:
バージョン2
バージョン1は使用可能ですが、バージョン2に変更すると、正しい結果は得られません.完全等価の形はバージョン2のifで>=を使うべきだと知っていますが、LGNMより大きい場合はないと思いますが、なぜ>=を==に置き換えるとエラーになるのでしょうか?
名手が伝言の中で解答を与えることを望んで、先に謝りました!
詳細:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1649
1.2テーマ説明:
AngelはMOLIGPYに捕まって刑務所に閉じ込められた.刑務所はNを1つ使うことができます×Mのマトリックスで説明すると、1
Angelの友達はAngelを救いに行きたいと思っています.彼の任務はAngelに近づくことだ.「Angelに近づく」という約束は、Angelが閉じ込められた位置に着くことを意味します.Angelの友达がある四角い格子を考えているが、四角い格子の中に警備員がいるなら、警備員を殺さなければ、この四角い格子に着くことができない.Angelの友人が上,下,左,右へ一歩移動するのに1単位時間,警備員を殺すのに1単位時間とする.Angelの友达がこんなに強くて、すべての警備員を殺すことができると仮定します.あなたの任務はAngelの友达がAngelに近づくのに少なくともどのくらいの時間がかかるかを計算することです.上、下、左、右にしか移動できません.壁は通過できません.
1.3入力説明
入力ファイルに複数のテストデータが含まれています.各テストデータの第1の動作は2つの整数NとMであり、次はN行であり、各行はM文字である:"."道路を表し、「a」はAngelを表し、「r」はAngelの友人を表し、「#」は壁を表し、「x」は警備員を表す(各テストデータには「a」と「r」の文字が1つしかないことに注意).ファイルの最後までデータを入力します.
1.4出力説明
入力ファイルのテストデータごとに、Angelに近い最小時間を示す整数を出力します.Angelに近づけない場合は、「PoorANGEL has to stay in the prison all his life.」と出力します.
二、考え方
問題の要求は,rから出発して,aまでの所要時間が最も短い経路を見つけ,最短時間を出力することである.
0.複数の経路が存在する可能性がある(また、ガードによる影響を考慮すると、ステップ数が最も少ない経路は必ずしも時間が最も短い経路ではない)ため、まず広さ優先アルゴリズムの採用が考えられる.2 D配列を使用して、ポイントに到達する最小時間を記録します.これにより、Angelを救出する最小時間を見つけることができます.
1.警備員については、その時点に到達するまでの時間が通常点よりも多くなるように簡単に処理することができる1
2.本題は比較的典型的な広さ優先アルゴリズムBFSで実現できる--Queueを確立し、次の点を順番に列挙し、新しい要求に合致する点を列挙する.QueueはC++が提供するタイプを直接使用することができますが、何を列挙するかは私たちに確定させます.ここでは,x,y,timeの3つの要素を含むNode構造体を構築し,前者は座標を示し,後者はその点に到達するのに要する時間を示す.
3.したがって、全体的な考え方は、r点から4方向に探索し、その点に到達した時間が、元の記録された到達点よりも短ければ、その点から新しい探索を継続する(この点を列に入れる)ことである.キュー内の点が全て探索された後、a点が最小時間(初期設定の最大値ではない)に対応すれば、Angelを救出することができる.
特筆すべきは、本題には大きな穴があることだ.
刑務所はNを1つ使うことができます×Mのマトリクスで説明すると、1」ですが、ZOJはテスト用例では200以上のデータを使っているはずなので、MAXを200にするとZOJでテストするときに「Wrong Answer」と報告して202に変更しなければOKではありません
これからZOJの問題をするにも配列境界を緩和すべきだ.
三、解答
完全なプログラムは以下の通りで、ZOJのテストに合格することができます.
/*
Rescue（ ），ZOJ1649
2016.05.26 Thu rainy by Pospro
http://blog.csdn.net/pospro
*/
#include
#include
#include
#define MAX 202
// ， ！！ ：1 Q;
int BFS()
{
int i;
int nextx, nexty, nexttime;
while(!Q.empty())
{
fnode=Q.front(); // ， ， pop，
Q.pop();
for(i=0;i<8;i=i+2) //
{
nextx=fnode.x+fx[i]; // x
nexty=fnode.y+fx[i+1]; // y
if(nextx<0||nextx>=N||nexty<0||nexty>=M||prison[nextx][nexty]=='#')
continue; // ， ；
if(prison[nextx][nexty]=='x')
nexttime=fnode.time+2; //
else
nexttime=fnode.time+1;
// ，
if(nexttime 四、疑問
この問題はすでに解けたが,まだ多くの疑問が残っているので,達人に知らせてもらいたい.
1.深さ優先アルゴリズムでこの問題を解くことができますか?理由は?
2.INTを使おうとしたMAX(#include)はLGMN(#define LGNM 1000000)の代わりに使われていますが、いったん置き換えると正確な結果が得られません.これはなぜですか?
3.BFS最後のif文についての質問
バージョン1:
if(mintime[ex][ey]バージョン2
if(mintime[ex][ey]==LGNM)
return -1;
else
return mintime[ex][ey];バージョン1は使用可能ですが、バージョン2に変更すると、正しい結果は得られません.完全等価の形はバージョン2のifで>=を使うべきだと知っていますが、LGNMより大きい場合はないと思いますが、なぜ>=を==に置き換えるとエラーになるのでしょうか?
名手が伝言の中で解答を与えることを望んで、先に謝りました!