C++14(g++5.4) 解法, 执行用时: 18ms, 内存消耗: 2016K, 提交时间: 2019-07-22 09:58:33

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+4,M=303,inf=16843009;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int mz[M][M];
struct  po{
	int x,y,t;
	po(int x=0,int y=0,int t=0):x(x),y(y),t(t){}
}que[M*M];
bool vis[M][M];
int main(){
	int n,x,y,t;
	memset(mz,1,sizeof(mz));
	
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&x,&y,&t);
		mz[x][y]=min(mz[x][y],t);
		for(int j=0;j<4;j++){
			int nx=x+dir[j][0],ny=dir[j][1]+y;
			if(nx>=0&&ny>=0)
				mz[nx][ny]=min(mz[nx][ny],t);
		}
	}

	int qf,qt=1;
	po u=po(0,0,0);
	que[qf=0]=u;
	vis[0][0]=true;
	if(mz[0][0]==inf){
		puts("0");
		return 0;
	}
	while(qf<qt){
		u=que[qf++];
		for(int i=0;i<4;i++){
			int nx=u.x+dir[i][0],ny=dir[i][1]+u.y;
			if(nx>=0&&ny>=0&&!vis[nx][ny]&&mz[nx][ny]>u.t+1){
				if(mz[nx][ny]==inf){
					printf("%d",u.t+1);
					return 0;
				}
				vis[nx][ny]=true;
				que[qt++]=po(nx,ny,u.t+1);
			}
		}
	}
	puts("-1");
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 1144K, 提交时间: 2020-03-28 20:40:41

#include <bits/stdc++.h>
using namespace std;
int m[305][305],b[305][305],ans=9999999;
void dfs(int x,int y,int t)
{
	if(m[x][y]<=t||t>=ans||t>=b[x][y])
	return ;
	b[x][y]=t;
	if(m[x][y]>9000000)
	{
        ans=min(t,ans);
        return;
    }
    dfs(x+1,y,t+1);
    if(x>=1)  
	dfs(x-1,y,t+1);
    dfs(x,y+1,t+1);
    if(y>=1)  
	dfs(x,y-1,t+1);
}
int main()
{
	memset(m,0x3f,sizeof(m));
    memset(b,0x3f,sizeof(b));
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	int p,q,o;
    	cin>>p>>q>>o;
    	m[p][q]=min(m[p][q],o);
        m[p+1][q]=min(m[p+1][q],o);
        if(p>=1)
        m[p-1][q]=min(m[p-1][q],o);
        m[p][q+1]=min(m[p][q+1],o);
        if(q>=1)
        m[p][q-1]=min(m[p][q-1],o);
	}
	dfs(0,0,0);
	if(ans==9999999)
    cout<<0-1<<endl;
    else
    cout<<ans<<endl;
	return 0;
}