[Codeforces Round #815 (Div. 2)] C. Corners

 

---

 

※. L자 모양 도형을 0으로 만들 수 있다. 이 작업을 거쳐 모든 수가 0으로 되게 하는 최대 횟수를 구하는 문제.

 

※. 최대한 많은 작업을 하려면 1을 겹치지 않게 0으로 만들어야 한다.

 

※. L모양에 0이 2개 있다면 최적

(1의 개수만큼 작업을 할 수 있다)

※. L모양에 0이 1개일 경우 이 한 번의 작업만 거치면 나머지는 위와 같이 최적의 작업을 할 수 있다.

(L도형 모두 0이 되기 때문에 이후의 L도형은 0이 2번 오게 할 수 있다.)

 

※. 셀에 1이 하나라도 있을 경우 무조건 한 번 이상의 작업을 수행해야 한다.(결과값에 1을 미리 더해준다.)

 (이후의 작업은 모두 최적의 작업을 할 수 있으므로 처음의 작업이 최적의 작업인지 아닌지만 확인해준다)

 

확인하는 방법은 다음과 같다.

 

※.모든 셀을 탐색하며  2*2의 사각형 안에 0개수에 따라 minn를 정한다.

(0이 없을 경우 최적의 작업을 할 수 없다. (사각형의 총합) 4-1 = 3)

(0이 하나 있을 경우 최적의 작업을 할수 없다. (사각형의 총합) 3-1 = 2)

(0이 두 개 있을 경우 최적의 작업이 가능하다. (사각형의 총합-1) = 1)

(0이 세 개 있을 경우 최적의 작업이 가능하다. 총합-1을 하면 0이 되어버린다. 따라서 이 경우 위와 같이 1로 만들어준다.)

 

처음 작업의 수는 다음과 같다.

※. 1(무조건 해야하는 작업) + sum(처음 작업의 2*2의 사각형의 총합) - minn(최적의 작업이면 sum과의 합이 0이 나와야 하고 아니면 1이 나와야한다.) 이 작업 뒤에는 전부 최적의 작업이 가능하므로 + (모든셀의 총합) - (처음 작업의 2*2사각형의 총합)을 해주면 결과값이 나온다.

 

식을 다시 정리하면

※. 1 + (모든 셀의 총합) - minn

 

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 			int n = Integer.parseInt(st.nextToken());
 			int m = Integer.parseInt(st.nextToken());
 			int sum = 0;
 			int[][] arr = new int[n][m];
 			
 			for(int i = 0; i < n; i++) {
 				String str = br.readLine();
 				for(int j = 0; j < m; j++) {
 					int a = str.charAt(j) - '0';
 					arr[i][j] = a;
 					sum += arr[i][j];
 				}
 			}
 			
 			int minn = Integer.MAX_VALUE;
 			for(int i = 0; i < n-1; i++) {
 				for(int j = 0; j < m-1; j++) {
 					int cnt = arr[i][j] + arr[i+1][j] + arr[i][j+1] + arr[i+1][j+1];
 					if(cnt != 0) {
 						minn = Math.min(minn, Math.max(1, cnt-1));
 					}
 				}
 			}
 			if(sum == 0)
 				sb.append(0).append('\n');
 			else
 				sb.append(1+sum-minn).append('\n');
 		}
 		System.out.println(sb);
 	}
}