P8230 地牢 题解

· · 题解

update:

性质：

首先，通过读题我们可以得出以下性质：无论按怎样的顺序击败敌人，先击败能力值小的敌人的方案总是最优的。

因为在击败敌人后，能力值可能会大于击败前不能击败的敌人。又因为只有当击败敌人后才能通过该格子，所以需要将当前不能击败的记录下来，等到能击败时再搜索一遍。

做法：

我们写一个函数，搜索在起点范围里面能到达并击败的敌人，如果可以直接击败该敌人，直接击败。如果不行，就先存储。

存储完后，在优先队列中从小到大击败，顺便再搜索。如果不能击败此敌人，说明后面更大的敌人也不能击败，直接退出。

最后更新起点坐标。

代码：

#include<bits/stdc++.h>
using namespace std;
int l,n,m;
long long now=1;
vector<long long>a[1000001]; 
int endx,endy;
struct shu {
    int value;
    int x;
    int y;
    bool operator () (const shu &a,const shu &b) const {
        return a.value>b.value;
    }
};
priority_queue<shu,vector<shu>,shu >q;
int tot;
int find(int x,int y) { //搜索当前能到达的地方。
    if(x<1||x>n||y<1||y>m||a[x][y]==-9||a[x][y]==-1||(endx==x&&endy==y))return 0;
    if(a[x][y]!=0&&a[x][y]!=-9&&a[x][y]!=-1) {
        if(now>=a[x][y])now+=a[x][y];//如果能击败，直接击败
        else{
            q.push({a[x][y],x,y});
            a[x][y]=-9;
            return 0;
        }
    }
    a[x][y]=-9;//避免重复搜索
    find(x+1,y);
    find(x,y+1);
    find(x-1,y);
    find(x,y-1);
    return 0;
}
int main() {
    scanf("%d%d%d",&l,&n,&m);
    int x=1,y=1;
    while(l--) {
        if(l==0){
            endx=-1,endy=-1;
        }
        tot=0;
        for(int i=1; i<=n; i++) {
            a[i].clear();
            a[i].push_back(0);
            for(int j=1; j<=m; j++) {
                int now;
                cin>>now;
                a[i].push_back(now);
                if(a[i][j]==-1) {
                    endx=i,endy=j;
                }
            }
        }
        find(x,y);
        while(!q.empty()) {
            shu top=q.top();
            if(top.value<=now) {
                now+=top.value;
                a[top.x][top.y]=0;
                find(top.x,top.y);
                q.pop();
            } else {
                break;
            }
        }
        priority_queue<shu,vector<shu>,shu >qw;
        q=qw;//注意清空队列
        x=endx,y=endy;//更新起点
    }
    cout<<now<<endl;
}