不知为何错了
查看原帖
不知为何错了
428444
Krisinsonia318楼主2021/9/26 21:13

用的搜索回溯,cpp,只对了#1、#2、#4、#8、#11,其他全是输出走不到的情况(-1)。

代码如下:(打了好久)

#include<bits/stdc++.h>
using namespace std;
int cin_n,cin_m,a[10][10],hp=6,ans,n1,m1,n2,m2,minn,f;
//cin_n和cin_m矩阵长和宽,a数组读入,hp血量,ans走的步数,
//n1,m1,n2,m2:起始点和家门口,minn求最少步数,f判断死亡,
//b数组判断格子是否走过
bool b[10][10];
void Search(int x,int y)
{
    if(hp==0)//是否死亡
    {
        f=0;
        return;
    }
	++ans;//走一步
	if(x==m2&&y==n2&&hp!=0)//是否到达终点
	{
		f=1;
		if(ans<minn)minn=ans;
	}
	else
	{
		b[x][y]=1;//标记为走过
		if(!b[x+1][y]&&x<m2&&a[x+1][y]!=0&&hp!=0)//左
		{
		    if(a[x+1][y]==4)//吃药
		        hp=6;
		    hp--;//减少血量
		    if(hp==0)//是否死亡
		    {
		        f=0;
		        return;
		    }
		    Search(x+1,y);
		    
		}
		if(!b[x][y+1]&&y<n2&&a[x][y+1]!=0&&hp!=0)//下
		{
		    if(a[x][y+1]==4)//同上
		        hp=6;
		    hp--;
		    if(hp==0)
		    {
		        f=0;
		        return;
		    }
		    Search(x,y+1);
		}
		if(!b[x-1][y]&&x>0&&a[x-1][y]!=0&&hp!=0)//右
		{
		    if(a[x-1][y]==4)
		        hp=6;
		    hp--;
		    if(hp==0)
		    {
		        f=0;
		        return;
		    }
		    Search(x-1,y);
		}
		if(!b[x][y-1]&&y>0&&a[x][y-1]!=0&&hp!=0)//上
		{
		    if(a[x][y-1]==4)
		        hp=6;
		    hp--;
		    if(hp==0)
		    {
		        f=0;
		        return;
		    }
		    Search(x,y-1);
		}
		--ans;
		b[x][y]=0;
	}
}
int main()
{
    cin>>cin_n>>cin_m;
    for(int i=1;i<=cin_n;i++)
        for(int j=1;j<=cin_m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]==2)//找起始点
            {
                n1=i;
                m1=j;
            }
            if(a[i][j]==3)//找结束点
            {
                n2=i;
                m2=j;
            }
        }
    f=0;
    ans=0;
    minn=cin_n*cin_m;//假设是走遍全图
    Search(n1,m1);
    if(f==0)cout<<-1;
    else cout<<ans;
    return 0;
}

求助!谢谢!

2021/9/26 21:13
加载中...