欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计蒜客习题:逃生

程序员文章站 2022-07-12 09:10:27
...

超时代码 ,超时的代码是用搜索写的,一直不知道为什么,就去搜了别人的题解,看到别的的做法确实比自己的暴力搜索快。

#include<iostream>
using namespace std;
int b[8]={1,0,-1,0,1,0,-1,0};
int c[8]={0,1,0,-1,0,-1,0,1};
int maxx=-99,a[1005][1005];
int n,m,v,x,y,cc;
void dfs1(int sx,int sy,int num)
{
	if(maxx>cc)
	return;
	int nx,ny;
	if(sx==n&&sy==m)
	if(num+a[nx][ny]>maxx)
	{
	maxx=num+a[nx][ny];
	return; 
	} 
	if(num<0)
	return;
	for(int i=0;i<=1;i++)
	{
		nx=sx+b[i];
		ny=sy+c[i];
		if(nx<1||ny<1||nx>n||ny>m)
		continue;
		dfs1(nx,ny,num+a[nx][ny]);
	}
	return;
}
void dfs2(int sx,int sy,int num)
{
	if(maxx>cc)
	return;
	int nx,ny;
	if(sx==1&&sy==1)
	if(num+a[nx][ny]>maxx)
	{
	maxx=num+a[nx][ny];
	return; 
	}
	if(num<0)
	return;
	for(int i=2;i<=3;i++)
	{
		nx=sx+b[i];
		ny=sy+c[i];
		if(nx<1||ny<1||nx>n||ny>m)
		continue;
		dfs2(nx,ny,num+a[nx][ny]);
	}
	return;
}void dfs3(int sx,int sy,int num)
{
	if(maxx>cc)
	return;
	int nx,ny;
	if(sx==n&&sy==1)
	if(num+a[nx][ny]>maxx)
		{
	maxx=num+a[nx][ny];
	return; 
	}
	if(num<0)
	return;
	for(int i=4;i<=5;i++)
	{
		nx=sx+b[i];
		ny=sy+c[i];
		if(nx<1||ny<1||nx>n||ny>m)
		continue;
		dfs3(nx,ny,num+a[nx][ny]);
	}
	return;
}void dfs4(int sx,int sy,int num)
{
	if(maxx>cc)
	return;
	int nx,ny;
	if(sx==1&&sy==m)
	if(num+a[nx][ny]>maxx)
		{
	maxx=num+a[nx][ny];
	return; 
	}
	if(num<0)
	return;
	for(int i=6;i<=7;i++)
	{
		nx=sx+b[i];
		ny=sy+c[i];
		if(nx<1||ny<1||nx>n||ny>m)
		continue;
		dfs4(nx,ny,num+a[nx][ny]);
	}
	return;
}
int main()
{
    std::ios::sync_with_stdio(false);
	cin>>n>>m>>x>>y>>v>>cc;
	for(int i=1;i<=m;i++)
	for(int j=1;j<=n;j++)
		cin>>a[i][j];
	dfs1(x,y,v);
    dfs2(x,y,v);
	dfs3(x,y,v);
	dfs4(x,y,v);
    if(maxx>cc)
	cout<<cc;
    else if(maxx<0)
        cout<<"-1";
    else
        cout<<maxx;
 }

ac代码

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
int n,m,x,y,v,c,map[1005][1005],f[1005][1005],dead[1005][1005];
int main()
{
    cin >> n >> m >> x >> y >> v >> c;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            cin >> map[i][j];
        }
    }
    memset(f,0,sizeof(f));
    memset(dead,0,sizeof(f));
    f[x][y] = v;
    //左上 
    for (int i=x; i>=1; i--)
    {
        for (int j=y; j>=1; j--)
        {
            if (i==x && j==y)
                continue;
            else if (i==x)
                f[i][j] = f[i][j+1]+map[i][j];
            else if (j==y)
                f[i][j] = f[i+1][j]+map[i][j];
            else
                f[i][j] = max(f[i+1][j],f[i][j+1])+map[i][j];
            if (f[i][j]<=0)
                f[i][j] = -10000000;
            if (f[i][j]>c)
                f[i][j] = c;
        }
    }
    //右下 
    for (int i=x; i<=n; i++)
    {
        for (int j=y; j<=m; j++)
        {
            if (i==x && j==y)
                continue;
            else if (i==x)
                f[i][j] = f[i][j-1]+map[i][j];
            else if (j==y)
                f[i][j] = f[i-1][j]+map[i][j];
            else
                f[i][j] = max(f[i-1][j],f[i][j-1])+map[i][j];
            if (f[i][j]<=0)
                f[i][j] = -10000000;
            if (f[i][j]>c)
                f[i][j] = c;
        }
    }
    //左下 
    for (int i=x; i<=n; i++)
    {
        for (int j=y; j>=1; j--)
        {
            if (i==x && j==y)
                continue;
            else if (i==x)
                f[i][j] = f[i][j+1]+map[i][j];
            else if (j==y)
                f[i][j] = f[i-1][j]+map[i][j];
            else
                f[i][j] = max(f[i-1][j],f[i][j+1])+map[i][j];
            if (f[i][j]<=0)
                f[i][j] = -10000000;
            if (f[i][j]>c)
                f[i][j] = c;
        }
    }
    for (int i=x; i>=1; i--)
    {
        for (int j=y; j<=m; j++)
        {
            if (i==x && j==y)
                continue;
            else if (i==x)
                f[i][j] = f[i][j-1]+map[i][j];
            else if (j==y)
                f[i][j] = f[i+1][j]+map[i][j];
            else
                f[i][j] = max(f[i+1][j],f[i][j-1])+map[i][j];
            if (f[i][j]<=0)
                f[i][j] = -10000000;
            if (f[i][j]>c)
                f[i][j] = c;
        }
    }
    if (max(max(f[1][1], f[n][m]), max(f[1][m], f[n][1]))<0)
        cout << -1 << endl;
    else
        cout << max(max(f[1][1], f[n][m]), max(f[1][m], f[n][1])) << endl;
    return 0;
}

如果是原点,跳过,原点不处理。
如果在同行同列也要单独处理,因为可能会导致这个点的数值来自不是这个方向上的区域。
如果人的生命值已经≤0,后来再变正,也没有意义,因为人已经死过了。所以可以处理为,如果人死了,就把他的生命值赋值为无限小。
如果人的生命值大于最大生命值,生命值维持在最大生命值。
这个两个for循环感觉非常巧妙,在遇到小于0的中间情况时,给他赋一个无限小的负数,然后继续往下走,四个方向写四个循环。