pypy3 解法, 执行用时: 6491ms, 内存消耗: 230656K, 提交时间: 2022-11-12 21:19:42

from typing import *
from collections import *
move=[[0,1],[0,-1],[1,0],[-1,0]]
def get(a:int,b:int,grid:List[List[int]])->List[List[int]]:
    q=deque([[a-1,b-1,0]])
    ans=[[-1]*2000 for i in range(2000)]
    ans[a-1][b-1]=0
    while q:
        arr=q.popleft()
        for m in move:
            x,y=arr[0]+m[0],arr[1]+m[1]
            if x<0 or x>=len(grid) or y<0 or y>=len(grid[0]) or ans[x][y]>=0 or grid[x][y]==-1:
                continue
            ans[x][y]=arr[2]+1
            q.append([x,y,arr[2]+1])
    return ans
n,m,x=map(int,input().split())
sx,sy,ex,ey=map(int,input().split())
grid=[]
for i in range(n):
    grid.append(list(map(int,input().split())))
ans=1000000
d1,d2=get(sx,sy,grid),get(ex,ey,grid)
for i in range(n):
    for j in range(m):
        if d1[i][j]>=0 and d2[i][j]>=0 and grid[i][j]>x:
            ans=min(ans,d1[i][j]+d2[i][j])
print(-1 if ans==1000000 else ans)

C++(g++ 7.5.0) 解法, 执行用时: 1124ms, 内存消耗: 49432K, 提交时间: 2022-11-11 19:25:08

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 1000000007

int i,j,k,n,m,t,a[2050][2050],f[2050][2050][2],dz;
vector<pair<int,int> >v={{0,1},{0,-1},{1,0},{-1,0}};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>t;
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)cin>>a[i][j];
	memset(f,-1,sizeof(f));
	queue<tuple<int,int,int> >q;
	q.push({x1,y1,0});
	f[x1][y1][0]=0;
	while(!q.empty()){
		auto [x,y,z]=q.front();q.pop();
		//printf("NMSL%d %d %d\n",x,y,z);
		for(auto [dx,dy]:v){
			dx+=x;dy+=y;dz=z;
			if(dx<1||dx>n||dy<1||dy>m)continue;
			if(a[dx][dy]==-1)continue;
			if(a[dx][dy]>t)dz=1;
			if(f[dx][dy][dz]!=-1)continue;
			f[dx][dy][dz]=f[x][y][z]+1;
			q.push({dx,dy,dz});
		}
	}
	cout<<f[x2][y2][1];
}

C++(clang++ 11.0.1) 解法, 执行用时: 2335ms, 内存消耗: 49404K, 提交时间: 2022-11-28 10:25:07

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int i,j,k,n,m,t,a[2050][2050],f[2050][2050][2],dz;
vector<pair<int,int> >v={{0,1},{0,-1},{1,0},{-1,0}};
int main() {
	cin>>n>>m>>t;
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)cin>>a[i][j];
	memset(f,-1,sizeof(f));
	f[x1][y1][0]=0;
	queue<tuple<int,int,int> >q;
	q.push({x1,y1,0});
	while(!q.empty()){
		auto [x,y,z]=q.front();q.pop();
		for(auto [dx,dy]:v){
			dx+=x;dy+=y;dz=z;
			if(dx<1||dx>n||dy<1||dy>m||a[dx][dy]==-1)continue;
			if(a[dx][dy]>t)dz=1;
			if(f[dx][dy][dz]!=-1)continue;
			f[dx][dy][dz]=f[x][y][z]+1;
			q.push({dx,dy,dz});
		}
	}
	cout<<f[x2][y2][1];
}