← 返回题目列表

AtCoder · pakencamp_2025_day3_g

G. 使 T

中文机器翻译题面 查看原题

配点 : 100 点

通知

已发现该问题的假设解决方案是不正确的,并且可能无法在合理的时间内解决。非常抱歉。此问题也将从环球杯中删除。

我觉得这个问题可以在“外星人必须与至少另外两个外星人牵手”的条件下提出。

問題文

x 坐标和 y 坐标是 小于 0 以上 N 的整数的网格点 有一个外星人站在 (x, y) (别处)。

合計 N^2 每个人类外星人都有四只手。只是距离 1 似乎是 2 人类外星人可以互相牵手(创建双向连接)。

一开始,一些外星人对已经牵着手,他们的状态如下。

  • A_{i,j} = 1 时,(i, j) 中的外星人 (i, j+1) 中的外星人已经手牵着手(0 \le i < N,\ 0 \le j < N-1)。

  • B_{i,j} = 1 时,(i, j) 中的外星人 (i+1, j) 中的外星人已经手牵着手(0 \le i < N-1,\ 0 \le j < N)。

您可以执行以下操作 可以重复超过 0 次。 选择一个

  • 只是距离 1 是 2 选择一个外星人并 2 与人牵手。

通过适当地执行这些操作,又一个 3 与人类外星人牵手的外星人数量 最大化。

制約

  • 2 \le N \le 500
  • A_{i,j} \in \lbrace 0,1\rbrace (0 \le i < N,\ 0 \le j < N-1)
  • B_{i,j} \in \lbrace 0,1\rbrace (0 \le i < N-1,\ 0 \le j < N)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_{0,0} A_{0,1} \dots A_{0,N-2}
\vdots
A_{N-1,0} A_{N-1,1} \dots A_{N-1,N-2}
B_{0,0} B_{0,1} \dots B_{0,N-1}
\vdots
B_{N-2,0} B_{N-2,1} \dots B_{N-2,N-1}

出力

又一个 3 打印与人类外星人牵手的外星人的最大数量。


入力例 1

4
000
010
010
000
0000
0110
0000

出力例 1

8

样本的初始状态如图1左侧所示。如图所示,另外 12 通过连接双手,总计 8 每个外星人都是 3 你可以与人牵手。这是可实现的最大值并且是最佳的。


入力例 2

7
001110
111011
100110
101111
100001
001001
010110
0101011
1001110
1101000
0001111
0111000
0110111

出力例 2

42