题解：P17836 二维市闯关

zzc2025 · 2026-11-08 20:15:12 · 题解

如果不考虑 \texttt{Infinity} 的情况就是直接跑一个最长路非常简单。

考虑 \texttt{Infinity} 什么时候出现，不难想到如果有任意两个相连的格子都大于 0 是可以来回跑来达到的。

但是马上就可以想到如果是两个正数中夹若干个非正数也是可能的，但这样太难判定了，我们可以发现其存在的充要条件就是存在任意两个相连的格子的和都大于 0。

然后直接跑最长路。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
/*
#pragma region 哈基米
*/
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
const int N=1e5+5;
int n,m,mp[N],dis[N];struct stu{int x,y,w;bool operator<(const stu &t)const{return w<t.w;}};
inline int d(int x,int y){return (x-1)*m+y;}
priority_queue<stu> q;
signed main(){
    // freopen("1.in" ,"r",stdin );
    n=read(),m=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp[d(i,j)]=read();
    for(int i=1;i<n;i++) for(int j=1;j<=m;j++) {
        if(mp[d(i,j)]+mp[d(i+1,j)]>0) {printf("Infinity\n");return 0;}
    }
    for(int i=1;i<=n;i++) for(int j=1;j<m;j++) {
        if(mp[d(i,j)]+mp[d(i,j+1)]>0) {printf("Infinity\n");return 0;}
    }
    memset(dis,-0x3f,sizeof(dis));dis[d(1,1)]=mp[d(1,1)];q.push((stu){1,1,dis[d(1,1)]});
    while(!q.empty()) {
        stu h=q.top();q.pop();
        const int x=h.x,y=h.y,w=h.w,u=d(x,y);
        if(w>=dis[u]) {
            if(1<x) {
                const int v=d(x-1,y),cost=w+mp[v];
                if(dis[v]<cost) {dis[v]=cost;q.push((stu){x-1,y,cost});}
            }
            if(x<n) {
                const int v=d(x+1,y),cost=w+mp[v];
                if(dis[v]<cost) {dis[v]=cost;q.push((stu){x+1,y,cost});}
            }
            if(1<y) {
                const int v=d(x,y-1),cost=w+mp[v];
                if(dis[v]<cost) {dis[v]=cost;q.push((stu){x,y-1,cost});}
            }
            if(y<m) {
                const int v=d(x,y+1),cost=w+mp[v];
                if(dis[v]<cost) {dis[v]=cost;q.push((stu){x,y+1,cost});}
            }
        }
    }
    printf("%lld\n",dis[d(n,m)]);
    return 0;
}