求助
  • 板块题目总版
  • 楼主ECEG
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/24 20:34
  • 上次更新2023/10/27 13:49:10
查看原帖
求助
601122
ECEG楼主2022/8/24 20:34
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,val;
};
int n,m,mp[34][34],x,y,jkx,jky,ans1=1e9+7,ans2=1e8,ans3,dis[34][34],vis[34][34][10004];
int dx[8]={-2,-2,-1,-1,1,1,2,2},dy[8]={1,-1,2,-2,2,-2,1,-1};
void bfs(){
	queue<node>q;
	q.push((node){x,y,0});
	for(int i=1;i<=30;++i)
		for(int j=1;j<=30;++j)
			dis[i][j]=1e9;
	dis[x][y]=0;
	while(q.size()){
		node u=q.front();q.pop();
		if(dis[u.x][u.y]>ans1||(dis[u.x][u.y]==ans1&&u.val>ans2))continue;
		if(u.x==2&&u.y==8&&u.val==5&&dis[u.x][u.y]==2)cout<<"asd\n";
		if(u.x==jkx&&u.y==jky){
			if(ans1>dis[u.x][u.y]){
				ans1=dis[u.x][u.y];
				ans2=1e8;
				ans3=0;
			}
			if(ans1==dis[u.x][u.y]){
				if(ans2>u.val){
					ans2=u.val;
					ans3=0;
				}
				if(ans2==u.val)ans3++;
			}
			continue;
		}
		for(int i=0;i<8;++i){
			int xx=u.x+dx[i],yy=u.y+dy[i];
			if(xx<1||yy<1||xx>n||yy>m)continue;
			if(xx==2&&yy==8&&u.val==4&&dis[u.x][u.y]==2)cout<<"jk\n";	
			if(mp[xx][yy]==1&&dis[u.x][u.y]<=dis[xx][yy]&&vis[xx][yy][dis[u.x][u.y]]<=2){
				q.push((node){xx,yy,u.val+1}),vis[xx][yy][dis[u.x][u.y]]++,dis[xx][yy]=dis[u.x][u.y];
			}
			else if(mp[xx][yy]==0&&dis[u.x][u.y]+1<=dis[xx][yy]&&vis[xx][yy][dis[u.x][u.y]+1]<=2)
				q.push((node){xx,yy,u.val+1}),vis[xx][yy][dis[u.x][u.y]+1]++,dis[xx][yy]=dis[u.x][u.y]+1;
		}	
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&mp[i][j]);
			if(mp[i][j]==3)x=i,y=j,mp[i][j]=1;
			if(mp[i][j]==4)jkx=i,jky=j,mp[i][j]=1;
		}
	}
	bfs();
	if(ans1==1e9+7)printf("-1");
	else printf("%d\n%d\n%d\n",ans1,ans2,ans3);
	return 0;
}

问题:jk 输出了2个,asd 输出了3个,都是一个点。

2022/8/24 20:34
加载中...