站外问题求助
  • 板块学术版
  • 楼主int4096
  • 当前回复18
  • 已保存回复18
  • 发布时间2021/8/21 10:35
  • 上次更新2023/11/4 09:50:29
查看原帖
站外问题求助
542452
int4096楼主2021/8/21 10:35

题目:

又到了掉落小鱼干的时间了!

每秒钟坐标(xi,yi)(xi,yi) 的位置上会出现一条小鱼干,猫女士想要用最短的等待时间带走k条小鱼干。

猫女士可以选择任意一个位置作为她的起始位置,只能选择东、西、南、北、东南、西南、东北、西北8个方向前进,一旦选择了方向就不能更改。她会沿着选择的方向冲刺,经过的位置如果有小鱼干都会带走,由于她的速度非常快,可以视为瞬间带走经过的所有位置上的鱼干。

请帮助猫女士求出她最短要等待几秒钟才能带走k条小鱼干。



输入格式

第一行两个正整数 n,k。

接下来 n 行,每行两个正整数 xi,yi。



输出格式

一个正整数 ans,表示最短的等待时间。如无解输出 -1。



样例输入/输出

【样例 1输入】

4 3
1 2
3 4
3 2
4 5

【样例 1 输出】

4

【样例 1 解释】

等待4秒,选择第1、2、4条小鱼干。

【样例 2 输入】

7 4
3 1
2 2
4 1
3 2
2 3
1 4
1 3

【样例 2输出】

6

数据范围

对于 100% 的数据,2≤k≤n≤106,1≤xi,yi≤105。

对于 50% 的数据,1≤xi,yi≤300。

我的代码:

#include <bits/stdc++.h>
using namespace std;
int n,k;
const int maxn=1e5+5;
struct node{
	int x,y,id;	
}a[maxn];
bool b[maxn][maxn];
int cnt;

int dx[8]={1,1,1,0,0,-1,-1,-1};
int dy[8]={-1,0,1,-1,1,-1,0,1};

int bfs(int time,int x,int y){
	if(cnt==k) return time;
	
	int tx=a[time].x,ty=a[time].y;
	if(b[tx][ty]==true) {
		cnt++;	
	}
	for(int i=0;i<8;i++){
		int xx=tx+dx[i],yy=ty+dy[i];
		if(xx==0 || xx==maxn || yy==0 || yy==maxn) break; 
		for(int i=1;i<=n;i++){
			if(a[i].x==xx && a[i].y==yy)
				bfs(time+1,xx,yy);
			else
				bfs(time,xx,yy);
		}
	}
}

int main(){
	cin>>n>>k;
	if(n<k){
		cout<<-1<<endl;
		return 0;
	} 
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		b[a[i].x][a[i].y]=true;
		a[i].id=i;
	}

	cout<<bfs(1,a[1].x,a[1].y);
	
	return 0;
}

运行不了有大佬帮帮忙吗

2021/8/21 10:35
加载中...