求助刚才T3
  • 板块学术版
  • 楼主_lqs_
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/2/11 18:04
  • 上次更新2023/10/24 01:06:50
查看原帖
求助刚才T3
664744
_lqs_楼主2023/2/11 18:04

莫名WA了#9,求助。

#include<bits/stdc++.h>
using namespace std;
#define N 3005
int n,m,i,j,ans=1e9,k,cnt=1e9,w,hei;
int mp[N][N],rem[N][N],a,b;
int dis1[N][N],q[N*N],u[N][N],h,t,x,y,nx,ny,flag,dis2[N][N];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
template<typename t> t &read(t &x){
    char c;int f=1;
    while(!isdigit(c=getchar()))f=(c=='-')?-1:1;
    x=c^'0';
    while(isdigit(c=getchar()))x=x*10+(c^'0');
    return x*=f;
}
void solve(){
	memset(dis1,1,sizeof(dis1));
	memset(dis2,1,sizeof(dis2));
	dis1[1][1]=0,q[1]=1*N+1;
	for(h=t=1;h<=t;h++){
		x=q[h]/N,y=q[h]%N;
		if(rem[x][y]==1 && dis1[x][y]<cnt) cnt=dis1[x][y],w=x*N+y,hei=mp[x][y];
		u[x][y]=0;
		for(i=0;i<=3;i++){
			nx=x+dx[i],ny=y+dy[i];
			if(nx>=1 && nx<=n && ny>=1 && ny<=m && dis1[nx][ny]>dis1[x][y]+1 && mp[nx][ny]!=0){
				dis1[nx][ny]=dis1[x][y]+1;
				if(!u[nx][ny]) u[nx][ny]=1,q[++t]=nx*N+ny;
			}
		}
	}
	dis2[n][m]=0,q[1]=n*N+m;
	for(h=t=1;h<=t;h++){
		x=q[h]/N,y=q[h]%N;
		u[x][y]=0;
		for(i=0;i<=3;i++){
			nx=x+dx[i],ny=y+dy[i];
			if(nx>=1 && nx<=n && ny>=1 && ny<=m && dis2[nx][ny]>dis2[x][y]+1 && mp[nx][ny]!=0){
				dis2[nx][ny]=dis2[x][y]+1;
				if(!u[nx][ny]) u[nx][ny]=1,q[++t]=nx*N+ny;
			}
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(rem[i][j]==1 && mp[i][j]!=0){
				if(mp[i][j]==hei) dis1[i][j]=min(dis1[i][j],dis1[w/N][w%N]+1);
				else dis1[i][j]=min(dis1[i][j],dis1[w/N][w%N]+2);
			}
			if(dis1[i][j]!=dis1[0][0] && dis2[i][j]!=dis2[0][0]) ans=min(ans,dis1[i][j]+dis2[i][j]);
		}
	}
	if(ans!=1e9) printf("%d",ans);
	else printf("-1");
}
int main(){
	read(n),read(m),read(k);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			read(mp[i][j]);
			if(mp[i][j]!=1) flag=1;
		} 
	}
	for(i=1;i<=k;i++){
		read(a),read(b);
		rem[a][b]=1;
	}
	solve();
	return 0;
}
2023/2/11 18:04
加载中...