英文

Time Limit：1s Memory Limit：256M

Description

Given a n*m map.A “Mengxin” is trapped.You are the one to rescue him.In the map,there are some guards,you must defeat the guards to get your way.Defeat one guard takes 1 min,move one step takes 1 min,each step you can only take one of 4 directions(up,down,left,right).Please tell us the least time you cost to rescue the guy.

Input

The first line contains two integers n,m
The next n lines,each line input m characters represent the map. 1<=n,m<=200
‘@’ is your position
‘#’ is obstacle
‘.’ means there is a way you can go
‘G’ means guard
‘M’ means the position of “Mengxin”.

Output

If you can save this guy,output the least time you cost,else,output “You can’t save Mengxin”

Sample Input1

7 8 #.#####. #.M#..@. #..#G... ..#..#.# #...##.. .#...... ........

Sample Output1

13

Sample Input2

2 2 M. G@

?Sample Output2

2

中文

時(shí)間：1s 空間：128M

題目描述：

在一個(gè)n?m的迷宮里，有一個(gè)萌新被困住了，你作為一個(gè)久經(jīng)碼場(chǎng)的戰(zhàn)士，決定去營(yíng)救萌新。地圖中還會(huì)有一些守衛(wèi)，你必須打敗守衛(wèi)才能通過守衛(wèi)所在的位置，打敗守衛(wèi)需要花費(fèi)1分鐘，移動(dòng)一步需要花費(fèi)一分鐘，每次你只能往上下左右某個(gè)方向移動(dòng)一步。問你最少需要花費(fèi)多少時(shí)間才能救到萌新。

輸入格式：

第一行輸入兩個(gè)整數(shù) n,m
接下來n行每行輸入m個(gè)字符
‘#’代表障礙物，無(wú)法直接通過
‘.’代表空地，可以直接通過
‘G’代表守衛(wèi)，你需要打敗他才能通過
‘M’代表萌新所在的位置
‘@’表示你所在的位置

輸出格式：

如果可以營(yíng)救到萌新，就輸出最少需要花費(fèi)的分鐘數(shù)
如果不可以，輸出“You can’t save Mengxin”

樣例輸入1：

7 8 #.#####. #.M#..@. #..#G... ..#..#.# #...##.. .#...... ........

樣例輸出1：

13

樣例輸入2：

2 2 M. G@

樣例輸出2：

2

約定：

1<=n,m<=200

注意：

以上輸入樣例中，用到的代碼片不是代碼，只是為了方便表示，謝謝。

提示：

這道題求的是最優(yōu)解，很容易就想到廣度優(yōu)先搜索（又稱寬度優(yōu)先搜，BFS），最先在隊(duì)列里遇到的答案一定就是最優(yōu)解了。廣度優(yōu)先搜索用隊(duì)列實(shí)現(xiàn)，用隊(duì)列的left來擴(kuò)展right來維持搜索。但還有一些小困難，比如打敗守衛(wèi)要1分鐘的問題。如何解決呢？我們可以假設(shè)我們?nèi)I(yíng)救她時(shí)，擁有一個(gè)技能可以秒殺有守衛(wèi)，這個(gè)技能要蓄力1分鐘，這是不是好理解一些呢？如果單純的認(rèn)為經(jīng)過守衛(wèi)的點(diǎn)耗時(shí)2min，博主認(rèn)為第一個(gè)掃到的終點(diǎn)不一定是最優(yōu)解（個(gè)人觀點(diǎn)，未經(jīng)嘗試）。請(qǐng)看代碼中的注解吧。具體代碼如下：

代碼：

#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <algorithm> #define N 200 using namespace std ; struct mrz {int x , y , z ;//x，y還是表示坐標(biāo)，z表示到該坐標(biāo)時(shí)的時(shí)間bool jn ;//jn時(shí)技能是否蓄力。初始條件是jn=0，當(dāng)在原地停留1min后，jn=1，打打掉守衛(wèi)后，jn=0； //我們不用當(dāng)心蓄力后還不打，卻繞路的問題，因?yàn)檫@肯定不是最優(yōu)解。如果蓄力后，繞路以后再打，也是可以的，不影響答案 } p [ N * N + 1 ] ; int x_c , y_c , x_z , y_z , n , m , l = 1 , r = 1 , ans = N*N*N ; int mp [ N + 1 ] [ N + 1 ] ;//查看地圖上的點(diǎn)是否走過 bool pd_a ( int k1 , int k2 )//判斷是否達(dá)到目標(biāo) {if ( k1 == x_z && k2 == y_z ) return true ;else return false ; } bool pd_b ( int k1 , int k2 )//判斷該點(diǎn)是否可以走 {if ( k1 >= 1 && k1 <= n && k2 >= 1 && k2 <= m && mp [ k1 ] [ k2 ] != 0 ) return true ;else return false ; } int main ( ) {scanf ( "%d%d" , & n , & m ) ;char c ;memset ( p , 0 , sizeof ( p ) ) ;memset ( mp , 0 , sizeof ( mp ) ) ;for ( int i = 1 ; i <= n ; i ++ ) for ( int j = 1 ; j <= m ; j ++)//生成地圖{cin >> c ;if ( c == '.' || c == 'M' ) mp [ i ] [ j ] = 1 ;if ( c == 'M' ){x_z = i ;y_z = j ;}if ( c == '@' ){x_c = i ;y_c = j ;}if ( c == 'G' ) mp [ i ] [ j ] = 2 ;}p [ 1 ] . x = x_c ;p [ 1 ] . y = y_c ;while ( l <= r){ // cout << p [ l ] . x << " " << p [ l ] . y << " " << p [ l ] . z << endl ; // for ( int i = 1 ; i <= n ; i ++ ) // { // for ( int j = 1 ; j <= m ; j ++ ) cout << mp [ i ] [ j ] ; // cout << endl ; // } // system ( "pause" ) ; // 以上代碼可以調(diào)時(shí)使用if ( pd_b ( p [ l ] . x + 1 , p [ l ] . y ) == true ){r ++ ;if ( mp [ p [ l ] . x + 1 ] [ p [ l ] . y ] == 1 ){ //最正常的情況，走空地p [ r ] . x = p [ l ] . x + 1 ;p [ r ] . y = p [ l ] . y ;p [ r ] . z = p [ l ] . z + 1 ;p [ r ] . jn = p [ l ] . jn ;mp [ p [ r ] . x ] [ p [ r ] . y ] = 0 ;} else{if ( p [ l ] . jn == 0 ){ //前方有守衛(wèi)，還未蓄力p [ r ] . x = p [ l ] . x ;p [ r ] . y = p [ l ] . y ;//原地不動(dòng)p [ r ] . z = p [ l ] . z + 1 ;//耗時(shí)1minp [ r ] . jn = 1 ;//蓄力} else{//前方有守衛(wèi)，蓄力完成p [ r ] . x = p [ l ] . x + 1 ;p [ r ] . y = p [ l ] . y ;p [ r ] . z = p [ l ] . z + 1 ;mp [ p [ r ] . x ] [ p [ r ] . y ] = 0 ;p [ r ] . jn = 0 ;}}if ( pd_a ( p [ r ] . x , p [ r ] . y ) == true && p [ r ] . z < ans ){ans = p [ r ] . z ;} //判斷答案}//以下是其他方向。廣搜代碼雖長(zhǎng)，但大同小異。if ( pd_b ( p [ l ] . x - 1 , p [ l ] . y ) == true ){r ++ ;if ( mp [ p [ l ] . x - 1 ] [ p [ l ] . y ] == 1 ){p [ r ] . x = p [ l ] . x - 1 ;p [ r ] . y = p [ l ] . y ;p [ r ] . z = p [ l ] . z + 1 ;p [ r ] . jn = p [ l ] . jn ;mp [ p [ r ] . x ] [ p [ r ] . y ] = 0 ;} else{if ( p [ l ] . jn == 0 ){p [ r ] . x = p [ l ] . x ;p [ r ] . y = p [ l ] . y ;p [ r ] . z = p [ l ] . z + 1 ;p [ r ] . jn = 1 ;} else{p [ r ] . x = p [ l ] . x - 1 ;p [ r ] . y = p [ l ] . y ;p [ r ] . z = p [ l ] . z + 1 ;mp [ p [ r ] . x ] [ p [ r ] . y ] = 0 ;p [ r ] . jn = 0 ;}}if ( pd_a ( p [ r ] . x , p [ r ] . y ) == true && p [ r ] . z < ans ){ans = p [ r ] . z ;}}if ( pd_b ( p [ l ] . x , p [ l ] . y + 1 ) == true ){r ++ ;if ( mp [ p [ l ] . x ] [ p [ l ] . y + 1 ] == 1 ){p [ r ] . x = p [ l ] . x ;p [ r ] . y = p [ l ] . y + 1 ;p [ r ] . z = p [ l ] . z + 1 ;p [ r ] . jn = p [ l ] . jn ;mp [ p [ r ] . x ] [ p [ r ] . y ] = 0 ;} else{if ( p [ l ] . jn == 0 ){p [ r ] . x = p [ l ] . x ;p [ r ] . y = p [ l ] . y ;p [ r ] . z = p [ l ] . z + 1 ;p [ r ] . jn = 1 ;} else{p [ r ] . x = p [ l ] . x ;p [ r ] . y = p [ l ] . y + 1 ;p [ r ] . z = p [ l ] . z + 1 ;mp [ p [ r ] . x ] [ p [ r ] . y ] = 0 ;p [ r ] . jn = 0 ;}}if ( pd_a ( p [ r ] . x , p [ r ] . y ) == true && p [ r ] . z < ans ){ans = p [ r ] . z ;}}if ( pd_b ( p [ l ] . x , p [ l ] . y - 1 ) == true ){r ++ ;if ( mp [ p [ l ] . x ] [ p [ l ] . y - 1 ] == 1 ){p [ r ] . x = p [ l ] . x ;p [ r ] . y = p [ l ] . y - 1 ;p [ r ] . z = p [ l ] . z + 1 ;p [ r ] . jn = p [ l ] . jn ;mp [ p [ r ] . x ] [ p [ r ] . y ] = 0 ;} else{if ( p [ l ] . jn == 0 ){p [ r ] . x = p [ l ] . x ;p [ r ] . y = p [ l ] . y ;p [ r ] . z = p [ l ] . z + 1 ;p [ r ] . jn = 1 ;} else{p [ r ] . x = p [ l ] . x ;p [ r ] . y = p [ l ] . y - 1 ;p [ r ] . z = p [ l ] . z + 1 ;mp [ p [ r ] . x ] [ p [ r ] . y ] = 0 ;p [ r ] . jn = 0 ;}}if ( pd_a ( p [ r ] . x , p [ r ] . y ) == true && p [ r ] . z < ans ){ans = p [ r ] . z ;}}l ++ ;}if ( ans == N * N * N ) cout << "You can't save Mengxin" ;//還有不能營(yíng)救的情況else cout << ans ;return 0 ; }

相關(guān)鏈接：

XJOI 題解小全：
https://blog.csdn.net/zj_mrz/article/details/80949787

XJOI 3330 Knight moving 騎士出行 題解：
https://blog.csdn.net/zj_mrz/article/details/81031135

XJOI 3393 序列 題解：
https://blog.csdn.net/zj_mrz/article/details/80948621

XJOI 3404 刷油漆 題解：
https://blog.csdn.net/zj_mrz/article/details/80949407

轉(zhuǎn)載于:https://www.cnblogs.com/zj-mrz/p/10122469.html

總結(jié)

以上是生活随笔為你收集整理的XJOI 3585 The rescue plan 营救计划 题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。