Portal

题意翻译

### 题意描述 CQXYM发现了一个大小为$n×m$的、由$n$行$m$列的格子组成的矩阵$A$。此矩阵的每一个方格要么是一个黑曜石块，要么是空的。 CQXYM可以用一次操作将一个黑曜石块挖掉变成空格子，或者是在空格子里放上黑曜石块。 （注意：$（x，y）$意思是纵坐标为$x$、横坐标为$y$的格子）（即$x$行$y$列） 现有一个$a×b$（$a$行$b$列）的矩阵$M$，当且仅当它满足如下条件时，它可以称为一个“下界传送门”： $a≥5$，$b≥4$。 对于所有$1<x<a$的$x$，格子$（x，1）$与格子$（x，b）$都有黑曜石块。 对于所有$1<x<b$的$x$，格子$（1，x）$与格子$（a，x）$都有黑曜石块。 对于所有的$1<x<a$，$1<y<b$，格子$（x，y）$为空格子。 $（1，1）$、$（1，b）$、$（a，1）$、$（a，b）$四个格子存不存在黑曜石块均可。 请注意：是$a$行、$b$列，不是$a$列、$b$行。 注意四个角的格子可以存在黑曜石块，也可能是空格子。 CQXYM想要知道使得此矩阵的至少一个子矩阵成为一个“下界传送门”所需的最小操作数。 （子矩阵的行数$a≥5$，列数$b≥4$） ### 输入格式 第一行包含数据的组数$t（t≥1）$。 对于每组数据，第一行包含矩阵的行数和列数$ n$,$m（5≤n≤400,4≤m≤400）$。 接下来的$n$行，每一行包含$m$个为$0$或$1$的数字。若第$i$行第$j$个数为$0$，$（i，j）$即为空格。反之，若数字为$1$，$（i，j）$即存在黑曜石块。 保证所有给出的$n$之和不超过$400$。 保证所有给出的$m$之和不超过$400$。 ### 输出格式 对于每组数据，输出一行一个整数$t$表示最小所需的操作数。两组数据的答案之间无需空行。 ### 样例 如上。 ### 说明/提示 第一组样例最终形成的“下界传送门”如下： ```cpp <pre class="verbatim"><br></br>1110<br></br>1001<br></br>1001<br></br>1001<br></br>0111<br></br> ``` ### 译者注释 一个最小的“下界传送门”如下,其中四角的格子为0或1均可 0110 1001 1001 1001 0110

题目描述

CQXYM found a rectangle $ A $ of size $ n \times m $ . There are $ n $ rows and $ m $ columns of blocks. Each block of the rectangle is an obsidian block or empty. CQXYM can change an obsidian block to an empty block or an empty block to an obsidian block in one operation. A rectangle $ M $ size of $ a \times b $ is called a portal if and only if it satisfies the following conditions: - $ a \geq 5,b \geq 4 $ . - For all $ 1 < x < a $ , blocks $ M_{x,1} $ and $ M_{x,b} $ are obsidian blocks. - For all $ 1 < x < b $ , blocks $ M_{1,x} $ and $ M_{a,x} $ are obsidian blocks. - For all $ 1<x<a,1<y<b $ , block $ M_{x,y} $ is an empty block. - $ M_{1, 1}, M_{1, b}, M_{a, 1}, M_{a, b} $ can be any type. Note that the there must be $ a $ rows and $ b $ columns, not $ b $ rows and $ a $ columns.Note that corners can be any type CQXYM wants to know the minimum number of operations he needs to make at least one sub-rectangle a portal.

输入输出格式

输入格式

The first line contains an integer $ t $ ( $ t \geq 1 $ ), which is the number of test cases. For each test case, the first line contains two integers $ n $ and $ m $ ( $ 5 \le n \le 400 $ , $ 4 \le m \le 400 $ ). Then $ n $ lines follow, each line contains $ m $ characters $ 0 $ or $ 1 $ . If the $ j $ -th character of $ i $ -th line is $ 0 $ , block $ A_{i,j} $ is an empty block. Otherwise, block $ A_{i,j} $ is an obsidian block. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 400 $ . It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 400 $ .

输出格式

Output $ t $ answers, and each answer in a line.

输入输出样例

输入样例 #1

1
5 4
1000
0000
0110
0000
0001

输出样例 #1

12

输入样例 #2

1
9 9
001010001
101110100
000010011
100000001
101010101
110001111
000001111
111100000
000110000

输出样例 #2

5

说明

In the first test case, the final portal is like this: ``` <pre class="verbatim"><br></br>1110<br></br>1001<br></br>1001<br></br>1001<br></br>0111<br></br> ```