2020 年百度之星·程序设计大赛 - 初赛一 Civilization BFS广搜

problem

Civilization Accepts: 619 Submissions: 2182
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
这是一个回合制游戏，每一回合开始前会进行上一回合的结算。

有一张 n*nn∗n 的棋盘，我们出生在一个初始位置 (x, y)(x,y)，现在我们要选择一个位置建设城市。

你的人物每回合可以移动到距离你曼哈顿距离不超过 2 的位置，移动完成后可以选择是否建立城市。

建立城市后，你的人物消失，成为一个人口为 1 的城市，这个人口要下回合才可以工作。如果不移动，直接在 (x,y) 建城，第 1 回合就可以开始工作。

对于城市的每个居民，你可以安排他到距离城市曼哈顿距离小于等于 3 的位置进行工作，此居民可以瞬间到达该位置，每个位置最多安排一个居民，失业的人口不会生产任何食物。

注意，城市位置上必须有一个居民在工作。

结算按照如下顺序：

如果位置 (i, j)(i,j) 上有一个工作居民，则获得 a[i][j]a[i][j] 的食物。
如果当前城市人口为 ii，且食物达到 8*i^28∗i
2
时，你获得一个新的居民，下一回合可以进行操作。
当结算后城市总人口达到 9 游戏结束。

初始食物数量为 0，人口上涨不会导致之前积累的食物消失。输出最少几个回合能让游戏结束。

Input
第一行一个正整数 test(1 \le test \le 10)test(1≤test≤10) 表示数据组数。

对于每组数据，第一行三个正整数 n(2 \le n \le 500), x(1 \le x \le n), y(1 \le y \le n)n(2≤n≤500),x(1≤x≤n),y(1≤y≤n)，分别表示棋盘大小和起始位置。

接下来 nn 行，每行 nn 个整数，第 ii 行第 jj 列的整数表示 a[i][j](1 \le a[i][j] \le 3)a[i]j。

Output
对于每组数据，一行一个整数表示答案。

Sample Input
Copy
1
10 9 8
1 2 2 1 2 3 1 1 2 1
2 1 3 3 3 2 3 2 3 1
1 1 3 1 1 3 2 2 1 2
3 1 3 1 3 3 1 3 1 3
3 2 3 1 3 1 2 2 2 1
2 3 2 3 2 2 3 1 2 3
3 1 3 3 2 2 3 2 3 3
1 3 3 2 3 2 2 2 1 1
3 3 1 2 3 2 1 2 1 2
1 1 3 1 3 1 1 1 3 3
Sample Output
39

solution

枚举每个点的位置，记录回合数，直接广搜。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int n,bx,by,a[1010][1010];
struct NODE{
	int x, y, step;
	NODE(int xx,int yy, int ss){x=xx;y=yy;step=ss;}
};
queue<NODE>q;
int vis[1010][1010], tim;

int seq[1010],cnt;
int getTime(int x, int y){
	cnt = 0;
	for(int i =-3; i<=3;i++){
		for(int j = -3; j<=3; j++){
			int xx = x+i, yy = y+j;
			if(i==0 && j==0)continue;
			if(xx<1||xx>n||yy<1||yy>n||abs(xx-x)+abs(yy-y)>3)continue;
			seq[++cnt]=a[xx][yy];
		}
	}
	sort(seq+1,seq+cnt+1,greater<int>());
	int num=1,roundnum=0,totfood=0,addfood=a[x][y];
	while(num<9){
		roundnum++;
		totfood+=addfood;
		if(totfood>=8*num*num){
			num++;
			addfood+=seq[num-1];
		}
	}
	return roundnum;
}

int ans;
void bfs(){
	while(!q.empty())q.pop();
	tim++;
	ans= getTime(bx,by);
	q.push(NODE(bx,by,0));
	vis[bx][by] = tim;
	while(!q.empty()){
		NODE tmp = q.front(); q.pop();
		int x = tmp.x, y = tmp.y;
		if(tmp.step+1+37>=ans)continue;
		for(int i=-2; i<=2; i++){
			for(int j=-2; j<=2; j++){
				int xx=x+i,yy=y+j;
				if(xx<1||xx>n||yy<1||yy>n||abs(xx-x)+abs(yy-y)>2||vis[xx][yy]==tim)continue;
				vis[xx][yy]=tim;
				ans = min(ans,tmp.step+1+getTime(xx,yy));
				q.push(NODE(xx,yy,tmp.step+1));
			}
		}
	}
}


int main(){
	int T; cin>>T;
	while(T--){
		cin>>n>>bx>>by;
		for(int i = 1; i<=n; i++)
			for(int j = 1; j <= n; j++)
				scanf("%d",&a[i][j]);
		bfs();
		cout<<ans<<"\n";
	}
	return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/107523424