洛谷P2802 回家-最新題解

洛谷P2802 回家-最新題解

寫這篇題解的原因：水經驗 洛谷方面增加了#11號資料，導致之前的題解代碼都無法AC，

題目傳送門
來看這個題解，應該都看過題了，下面水字數的粘貼可以直接跳過！

小H在一個劃分成了n*m個方格的長方形封鎖線上， 每次他能向上下左右四個方向移動一格（當然小H不可以靜止不動），
但不能離開封鎖線，否則就被打死了， 剛開始時他有滿血6點，每移動一格他要消耗1點血量，一旦小H的 血量降到 0， 他將死去，
他可以沿路通過拾取滑鼠（什么鬼，，，）來補滿血量，只要他走到有滑鼠的格子，他不需要任何時間即可拾取，格子上的滑鼠可以瞬間補滿，所以每次經過這個格子都有滑鼠，就算到了某個有滑鼠的格子才死去，
他也不能通過拾取滑鼠補滿 HP， 即使在家門口死去， 他也不能算完成任務回到家中，

地圖上有 5 種格子：

數字 0： 障礙物，

數字 1： 空地， 小H可以自由行走，

數字 2： 小H出發點， 也是一片空地，

數字 3： 小H的家，

數字 4： 有滑鼠在上面的空地，

小H能否安全回家？如果能， 最短需要多長時間呢？
輸入格式
第一行兩個整數n,m， 表示地圖的大小為n*m，
下面 n 行， 每行 m 個數字來描述地圖，
輸出格式
一行， 若小H不能回家， 輸出-1,否則輸出他回家所需最短時間，
輸入樣例：
3 3
2 1 1
1 1 0
1 1 3
輸出樣例：
4

這個題呢…很常規的DFS，
遍歷所有狀態，找到“回家”的最短時間（路線），
但…為了防止TLE，要進行剪枝，就是用一個bool或者你想用啥用啥，能夠記錄某個點是否使用過就可！避免重復性操作！

九十分代碼：

#include<iostream>
#include<cstring>
using namespace std;

int n, m,ans=999999;//n,m是地圖的范圍，ans最優答案
int map[150][150],book[150][150];//map存盤地圖資訊，book標記某點是否走過
int _next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };//存盤往 上 下 左 右 走的坐標變化
#define min(x,y) (x>y?y:x)
void dfs(int hp, int i, int j, int _time)//hp 走到（i,j）點的血量 _time走到(i,j)點用的時間
{
	if (hp == 0 || map[i][j] == 0||book[i][j]) return;
	//如果hp=0，map[i][j]=0（出界或者該點為障礙物），book[i][j]==1 該點走過，回傳
	if (map[i][j] == 3)//到家，更新ans
	{
		ans = min(ans, _time);
		return;
	}
	if (map[i][j] == 4) hp = 6;//撿到血包
	for (int z = 0; z < 4; z++) {//通過回圈，實作上下左右移動
		book[i][j] = 1;//標記使用
		dfs(hp - 1, i + _next[z][0], j + _next[z][1], _time + 1);
		book[i][j] = 0;//釋放該點
	}
	return;
}

int main()
{
	while (cin >> n >> m)
	{
		ans = 999999;
		memset(map, 0, sizeof(map));
		pair<int, int> strat;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				cin >> map[i][j];
				if (map[i][j] == 2) strat.first = i, strat.second = j;//記錄起始點
			}
		dfs(6, strat.first, strat.second, 0);
		if (ans == 999999) cout << -1 << endl;//如果ans沒有發生更新，則無法到達
		else cout << ans << endl;
	}
	return 0;
}

上面代碼可以通過以前的十個資料，但新增加的11號資料無法通過！
我們先來看一下十一號資料：

輸入
7 6
2 0 0 0 0 0
1 0 0 0 0 0
1 1 4 0 0 0
1 0 0 0 0 0
1 1 1 1 1 3
4 0 1 0 4 0
0 0 4 0 0 0
輸出：
15

這組資料有什么特別之處呢？
手動走一下就會發現，通過（6，1）（6，5）兩處的加血，可以長續航的到達終點，這就要求出現**(5,1)->(6,1)->(5,1)**->(5,2)->…這種重復性路線，
那么這種情況就與我們book的作用沖突！
如果我們去掉book呢？

實踐證明：重復性操作是不能容忍的！
因此，我們接下來要考慮，如何剪掉重復性操作的同時，把“能量供給”操作給保留！
在這方面思考，就有了接下來的100分代碼，

#include<iostream>
#include<cstring>
using namespace std;

int n, m,ans=999999;
int map[150][150];
pair<int,int>book[150][150];//第一個int 裝該點有沒有走過   第二個int 如果該點走過，走過時的hp為多少
int _next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
#define min(x,y) (x>y?y:x)
void dfs(int hp, int i, int j, int _time)
{
	if (hp == 0 || map[i][j] == 0) return;
	if (book[i][j].first==1&&book[i][j].second > hp) return;
	//如果該點走過，且這一次走過時hp小于之前走過時hp，表明沒有被補給！那么就屬于違法操作，return掉
	//如果first=0->沒有走過，second<hp->經過補給操作,那么該點就是合法點
	if (map[i][j] == 3)
	{
		ans = min(ans, _time);
		return;
	}
	if (map[i][j] == 4)  hp = 6;

	for (int z = 0; z < 4; z++) {
		book[i][j].first = 1, book[i][j].second = hp;//更新該點走過的狀態
		dfs(hp - 1, i + _next[z][0], j + _next[z][1], _time + 1);
		book[i][j].first = 0, book[i][j].second = 0;//釋放該點
	}
	return;
}

int main()
{
	while (cin >> n >> m)
	{
		ans = 999999;
		memset(map, 0, sizeof(map));
		pair<int, int> strat;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				cin >> map[i][j];
				if (map[i][j] == 2) strat.first = i, strat.second = j;
			}
		dfs(6, strat.first, strat.second, 0);
		if (ans == 999999) cout << -1 << endl;
		else cout << ans << endl;
	}
	return 0;
}

小白碼字不易，客官可否將小贊贊留下~
問題交流：1272607918@qq.com