題目描述 小H在一個劃分成了nm個方格的長方形封鎖線上， 每次他能向上下左右四個方向移動一格（當然小H不可以靜止不動）， 但不能離開封鎖線，否則就被打死了， 剛開始時他有滿血6點，每移動一格他要消耗1點血量，一旦小H的 血量降到 0， 他將死去， 他可以沿路通過拾取滑鼠（什么鬼，，，）來補滿血量，只要他走到有滑鼠的格子，他不需要任何時間即可拾取，格子上的滑鼠可以瞬間補滿，所以每次經過這個格子都有滑鼠，就算到了某個有滑鼠的格子才死去， 他也不能通過拾取滑鼠補滿 HP， 即使在家門口死去， 他也不能算完成任務回到家中，
地圖上有 5 種格子：
數字 0： 障礙物，
數字 1： 空地， 小H可以自由行走，
數字 2： 小H出發點， 也是一片空地，
數字 3： 小H的家，
數字 4： 有滑鼠在上面的空地，
小H能否安全回家？如果能， 最短需要多長時間呢？
輸入格式 第一行兩個整數n,m， 表示地圖的大小為nm，
下面 n 行， 每行 m 個數字來描述地圖，
輸出格式 一行， 若小H不能回家， 輸出-1,否則輸出他回家所需最短時間，
輸入輸出樣例 輸入 #1
復制
3 3
2 1 1
1 1 0
1 1 3
輸出
#1
復制
4
說明/提示 1<=n,m<=9
思路：dfs挺不錯的一道題目，一開始看資料量會發現很小，但是如果不仔細看的話，會出現很多錯誤，首先要注意剪枝，如果說當前步數已經大于等于當前的最小值了，就不需要往下走了，因為再走也是枉然，其次就是每一個格子都有可能再次走到，但是走到的時候，能量值是不一樣的，因此在標記的時候需要開一個三維陣列進行標記，
代碼如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
const int N = 11;
int sx,sy,ex,ey;
int g[N][N];
bool st[N][N][7];
int flag = 0;
int res = 0x3f3f3f3f;
int nex[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int x,int y,int health,int step)
{
if(health==0) return;
if(step>=res) return ;
if(g[x][y]==3)
{
res = min(res,step);
flag = 1;
return;
}
if(g[x][y]==4) health=6;
for(int i=0;i<4;i++)
{
int tx = x+nex[i][0];
int ty = y+nex[i][1];
if(tx<1||tx>n||ty<1||ty>m||st[tx][ty][health-1]) continue;
if(!g[tx][ty]) continue;
st[tx][ty][health-1]=1;
dfs(tx,ty,health-1,step+1);
st[tx][ty][health-1]=0;
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>g[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(g[i][j]==2)
{
sx = i;
sy = j;
}
if(g[i][j]==3)
{
ex = i;
ey = j;
}
}
st[sx][sy][6]=true;
dfs(sx,sy,6,0);
if(res==0x3f3f3f3f) printf("-1");
else printf("%d",res);
return 0;
}努力加油a啊
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259021.html
標籤：其他
上一篇：牛客OI周賽13-普及組