第7回日本情報オリンピック 春合宿 1日目 「インフルエンザ」 (Flu)

バケット法を使うという解法もあるけど実は使わなくても可能という問題。

探索＆再帰＆枝刈り

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> P;
int n,m,d,k;
bool used[100002];
int ch[1002][1002];
int z[100002][2];
vector<int> e[100002];
int ans = 0;
int nd[3] = {1,-1};
int main(){
	scanf("%d%d%d%d",&n,&m,&d,&k);
	d = d*d;
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&z[i][0],&z[i][1]);
		ch[z[i][0]][z[i][1]] = i;
	}

	for(int i = 1;i <= n;i++){
		int na = z[i][0];
		int nb = z[i][1];
		for(int a = 0;a <= d;a++){
			for(int b = 0;a*a + b*b <= d;b++){
					if(a == 0 && b == 0)continue;
					for(int s = 0;s < 2;s++){
						if(a == 0 && s == 1)break;
						for(int t = 0;t < 2;t++){
							if(b == 0 && t == 1)break;
							int naa = na + a*nd[s];
							int nbb = nb + b*nd[t];
							if(naa <= 1000 && naa >= 0 && nbb <= 1000 && nbb >= 0){
								if(ch[naa][nbb])e[i].push_back(ch[naa][nbb]);
							}
						}
					}
			}
		}
	}
	memset(used,false,sizeof(used));

	priority_queue<P,vector<P>,greater<P> > que;

	que.push(P(0,1));

	while(!que.empty()){
		P p = que.top(); que.pop();
		int fir = p.first;
		int sec = p.second;
		if(used[sec] == true)continue;
		used[sec] = true;
		if(fir > k){
			break;
		}else if(k >= fir && fir + m > k){
			ans++;
		}
		for(int i = 0;i < e[sec].size();i++){
			int to = e[sec][i];
			if(used[to] == true)continue;
			que.push(P(fir+1,to));
		}
	}

	printf("%d\n",ans);

	return 0;
}