页面无法加载？点击这里可能会修复。
Placeholder

#10366

스퀘어 댄스 40s 1024MB

问题

당신은 국제적인 댄스 대회를 기획하고 있다. 현재 다음은 모두 준비되어 있다:

  • 단위 정사각형 칸들로 이루어진 R행 C열의 댄스 플로어,
  • R × C명의 참가자,
  • 최첨단 자동 심판 시스템.

하지만 아직 관객이 없다! 대회가 충분히 흥미롭지 않을까 걱정되어, 대회의 흥미도(interest level)를 계산하는 방법을 고안했다.

각 참가자는 플로어의 한 칸을 차지하고, 탈락할 때까지 그 칸에 머문다. 참가자 x의 방위 이웃(compass neighbor)이란, x와 같은 행 또는 같은 열에 있으면서, x와 y 사이에 아직 남아 있는 참가자가 하나도 없도록 선택한 다른 참가자 y를 말한다. 각 참가자는 방위 이웃을 0명에서 4명까지 가질 수 있고, 한 직교 방향의 다른 참가자들이 모두 탈락하면 그 수는 감소할 수 있다.

대회는 라운드 단위로 진행된다. i라운드와 i+1라운드 사이에, 어떤 참가자 d가 i라운드 동안 적어도 한 명의 방위 이웃을 가지고 있었고, d의 실력치가 d의 모든 방위 이웃들의 실력치 평균보다 엄격히 작다면, d는 탈락하여 i+1, i+2, i+3, ... 라운드에는 참가하지 않는다. i라운드와 i+1라운드 사이에 다른 탈락이 일어날 때, d는 여전히 자신의 다른 방위 이웃들의 이웃으로 계산된다는 점에 유의하라. 방위 이웃이 전혀 없는 참가자는 절대 탈락하지 않는다. 어떤 라운드 이후에 아무도 탈락하지 않으면 대회는 종료된다.

한 라운드의 흥미도는 그 라운드에서 춤추는 참가자들의 실력치 합이다. (그 라운드와 다음 라운드 사이에 탈락할 예정인 참가자도 포함한다.) 대회의 흥미도는 모든 라운드의 흥미도를 합한 값이다.

1라운드에 플로어 위에 있는 댄서들의 실력치가 주어질 때, 대회의 흥미도는 얼마인가?


输入

입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 먼저 두 정수 R, C가 주어진 한 줄로 시작한다. 그 다음 R줄이 이어지며 각 줄에는 C개의 정수가 주어진다. i번째 줄의 j번째 값 Si, j는 플로어의 i행 j열 칸에 있는 댄서의 실력치이다.


输出

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 대회의 흥미도이다.


示例 

4
1 1
15
3 3
1 1 1
1 2 1
1 1 1
1 3
3 1 2
1 3
1 2 3
Case #1: 15
Case #2: 16
Case #3: 14
Case #4: 14
샘플 케이스 #1에서는 무용수가 한 명뿐이다. 이 무용수는 방향 이웃이 없으므로 한 라운드만 춤을 추고 대회가 끝난다. 따라서 답은 무용수의 실력치인 15이다. 샘플 케이스 #2에서 첫 라운드의 흥미도는 1+1+1+1+2+1+1+1+1=10이다. 가운데도 아니고 모서리도 아닌 무용수들의 실력치는 1이지만, 그들의 방향 이웃 평균은 4 / 3으로 1보다 크므로 탈락한다. 두 번째 라운드의 무대는 다음과 같다: 1 . 1 . 2 . 1 . 1 이 라운드가 마지막이다. 모서리의 무용수들은 각각 두 방향 이웃을 가지지만, 그 평균 실력치는 자기 자신과 같다. 가운데 무용수는 방향 이웃이 없다. 이 라운드의 흥미도는 1+1+2+1+1=6이다. 따라서 전체 대회의 흥미도는 10+6=16이다. 샘플 케이스 #3에서는 실력치 1인 무용수가 첫 라운드 후 탈락하고, 나머지 두 명이 남는다. 두 번째 라운드에서 나머지 두 무용수가 서로 방향 이웃이 되며, 그 결과 실력치 2인 무용수가 탈락한다. 세 번째 라운드에는 무용수 한 명만 남으므로 이것이 마지막 라운드다. 각 라운드의 흥미도는 6, 5, 3이므로 전체 흥미도는 14이다.

来源

GCJ 2020r1a C

需要登录才能编写代码。