题目:
又到了掉落小鱼干的时间了!
每秒钟坐标(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;
}
运行不了有大佬帮帮忙吗