2020 年百度之星·程序設計大賽 - 初賽一 Civilization BFS廣搜

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

枚舉每個點的位置，記錄回合數，直接廣搜。

#include #include #include #include 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;} }; queueq; 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 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<

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

5G游戲 大賽

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。