本蒟蒻第一次发题解
简单的DFS
我也只做了一个晚上，大错不犯，小错不断直到旁边的@哈哈哈哈。帮我揪出了问题
来自本蒟蒻的忠告： 为避免陶片放逐，请勿复制代码
正经的的来了
题目疑点！！！
-
即使在家门口死去， 他也不能算完成任务回到家中。（这说明进入dfs后要先判断血量）
-
他可以沿路通过拾取鼠标来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取（如果进入的格子有鼠标，血量直接补满，但他的血量要大于0）
基本思路！！！
-
首先，这道题是简单的DFS，DFS可以传4个参数，横坐标，纵坐标，血量，步数。为了重复走，（导致CPU烤鱼），我们可以开一个bool数组记录是否走过。
-
这道题求的是最少的步数，我们可以用打擂的方式求出最少的步数，定义一个Min为无限大，如果步数比Min少就更新，在输出的过程中，我们可以判断Min的值是否还为无限大，如果为无限大，就说明没有更新（也就是走不到）就输出无解
诚恳第附上代码!!!
#include<bits/stdc++.h>//万能头
using namespace std;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//方向数组
char a[10][10];//存图
bool c[10][10];//记录是否走过
int n,m,x11,x22,y11,y22,/*起点与重点*/Min=0x7f7f7f7f;//无限大
void dfs(int x,int y,int z,int k)//横坐标，纵坐标，血量，步数
{
z--;//进入就血量--
if(z==0||k>Min)
{
return; //如果血量为0或步数已超过Min就退出
}
if(a[x][y]=='3')
{
Min=min(Min,k); //如果到达终点，更新Min
return;
}
if(a[x][y]=='4')//判断可不可以回血
{
z=6;
}
k++;//步数++
for(int i=0;i<4;i++)
{
int tx=x+dir[i][0];
int ty=y+dir[i][1];//模拟方向
if(c[tx][ty]==true&&tx>=1&&tx<=n&&ty>=1&&ty<=m ) //判断出界和是否走过
{
c[x][y]=false;//赋值，避免重复走
dfs(tx,ty,z,k);//继续DFS
c[x][y]=true;//把值修改为没走过
}
}
}
int main()
{
memset(c,true,sizeof(c));//数组赋初值
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='0')//如果有墙就判定为不能走 ，布尔值为假，就不能搜素
{
c[i][j]=false;
}
if(a[i][j]=='2') //记录起点
{
x11=i;
y11=j;
}
if(a[i][j]=='3')// 记录终点
{
x22=i;
y22=j;
}
}
dfs(x11,y11,6,0); //开始搜索
if(Min!=0x7f7f7f7f)
cout<<Min;
else cout<<-1; //完美输出
return 0;//结束
}
无注释版（想得周到吧？）
#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char a[10][10];
bool c[10][10];
int n,m,x11,x22,y11,y22,Min=0x7f7f7f7f;
void dfs(int x,int y,int z,int k)
{
z--;
if(z==0||k>Min)
{
return;
}
if(a[x][y]=='3')
{
Min=min(Min,k);
return;
}
if(a[x][y]=='4')
{
z=6;
}
k++;
for(int i=0;i<4;i++)
{
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(c[tx][ty]==true&&tx>=1&&tx<=n&&ty>=1&&ty<=m )
{
c[x][y]=false;
dfs(tx,ty,z,k);
c[x][y]=true;
}
}
}
int main()
{
memset(c,true,sizeof(c));
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]=='0')
{
c[i][j]=false;
}
if(a[i][j]=='2')
{
x11=i;
y11=j;
}
if(a[i][j]=='3')
{
x22=i;
y22=j;
}
}
dfs(x11,y11,6,0);
if(Min!=0x7f7f7f7f)
cout<<Min;
else cout<<-1;
return 0;
}
本蒟蒻再次提醒
道路千万条，红名第一条。
刷题不规范，棕名两行泪