小码王集训营T125628异星矿区题解
2026-08-10 20:38:26
发布于：广东
2阅读
0回复
0点赞
题目背景
在遥远的异星，有一片巨大的网格状矿区，里面蕴藏着丰富的能量矿石。
题目描述
矿区可以看作是一个 N 行 M 列的二维矩阵。位于第 i 行第 j 列的区域中，有价值为 w
i,j
的能量矿石。
一辆探测车从矿区的左上角 (1,1) 出发，目标是到达右下角 (N,M)。探测车每次只能向 右 移动一格或向 下 移动一格。每进入一个格子（包括起点和终点），探测车就会收集该格子里的所有能量矿石。
然而，异星的环境非常极端。如果探测车在同一个方向上连续行驶的步数超过了 K 步，其引擎就会过热爆炸。也就是说：
探测车不能连续向下移动超过 K 次。
探测车不能连续向右移动超过 K 次。
请你计算出，探测车在安全到达终点 (N,M) 的前提下，最多能收集到多少总价值的能量矿石？如果无论如何探测车都无法安全到达终点，请输出 -1。
//dp[i][j]
//dp[i+1][j]+=d[i][j];
//dp[i][j+1]+=d[i][j];
#include<bits/stdc++.h>
using namespace std;
const int N=500+10;
#define ll long long
ll a[N][N],dp[N][N];
bool vis[N][N][12][2];//vis[i][j][k][d] 在d方向走k次走到(i,j)坐标是否到达
ll res[N][N][12][2];// 在d方向走k次走到(i,j)坐标对应的答案
//step：沿一个方向走的步数，dire：方向 0:向右，1：向下
int n,m,k;
bool check(int x,int y){
if(x<1||x>n||y<1||y>m)return false;
return true;
}
struct Node{
int x,y;
int step,dire;
};
ll ans=-1;
void bfs(){
queue<Node>que;
que.push({1,1,0,0});
vis[1][1][0][0]=1;//为起点打上标记 //分层图
res[1][1][0][0]=a[1][1];
while(que.size()){
auto cur=que.front();que.pop();
// cout<<cur.x<<' '<<cur.y<<' '<<cur.step<<' '<<cur.dire<<' '<<res[cur.x][cur.y][cur.step][cur.dire]<<endl;;
if(cur.x==n&&cur.y==m){
ans=max(ans,res[cur.x][cur.y][cur.step][cur.dire]);
}
//继续沿着方向走
if(cur.step<k){
int nx=cur.x,ny=cur.y;
if(cur.dire==0)ny++;
else nx++;
if(check(nx,ny)){
if(vis[nx][ny][cur.step+1][cur.dire]==0){
que.push({nx,ny,cur.step+1,cur.dire});
vis[nx][ny][cur.step+1][cur.dire]=1;
}
res[nx][ny][cur.step+1][cur.dire]=max(res[nx][ny][cur.step+1][cur.dire],
res[cur.x][cur.y][cur.step][cur.dire]+a[nx][ny]);
}
}
//拐弯
// if(cur.step!=k){
int nx=cur.x,ny=cur.y;
if(cur.dire==1)ny++;
else nx++;
if(check(nx,ny)){
if(vis[n
/*//DP
//dp[i][j]
//dp[i+1][j]+=d[i][j];
//dp[i][j+1]+=d[i][j];
#include<bits/stdc++.h>
using namespace std;
const int N=500+10;
#define ll long long
ll dp[N][N][12][2];
ll a[N][N];
int n,m,k;
ll ans=-1;
void solve(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
// dp[1][1][5][0];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int step=0;step<=k;step++)
for(int dire=0;dire<2;dire++){
dp[i][j][step][dire]=-1e18;
}
dp[1][1][0][0]=a[1][1];//起点保留
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int step=0;step<=k;step++)
for(int dire=0;dire<2;dire++){
if(dp[i][j][step][dire]==-1e18)continue;
if(i==n&&j==m)ans=max(ans,dp[i][j][step][dire]);
if(step<k){
int nx=i,ny=j;
if(dire==0)ny++;else nx++;
dp[nx][ny][step+1][dire]=max(dp[nx][ny][step+1][dire],dp[i][j][step][dire]+a[nx][ny]);
}
int nx=i,ny=j;
if(dire==1)ny++;else nx++;
dp[nx][ny][1][1-dire]=max(dp[nx][ny][1][1-dire],dp[i][j][step][dire]+a[nx][ny]);
}
cout<<ans<<endl;
}
int main(){
int t=1;
freopen("y.in", "r", stdin);
freopen("y.out", "w", stdout);
// cin>>t;
while(t--){
solve();
}
}
*/
这里空空如也
有帮助，赞一个