计蒜客习题:逃生
程序员文章站
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的中间情况时,给他赋一个无限小的负数,然后继续往下走,四个方向写四个循环。