놀이공원 - 구름LEVEL
놀이공원
Press the right button to connect the device.
Quiz Info
놀이공원
100points
Participant
1129
Solved Rate
58.2%
71
53

 어느 한 도시에서는 공장 단지가 부도가 나게 되어 넓은 공터가 경매에 올라오게 되었다. 이 공터는 가로와 세로가 각각 N km인 정사각형 모양이며 가로와 세로가 1 km인 정사각형 격자 모양으로 영역을 나누어 개별적으로 판매하고 있다. 

 그 도시에 살고있던 한 부자 경영인은 평소 자신이 기획해오던 놀이공원 건설 프로젝트를 몰래몰래 진행하기로 결정하였다. 때마침 경매에 올라온 이 공터에 관심을 가지게 된 경영인은 판매 중인 땅들 중 일부에는 기존의 공장에서 배출 된 폐기물들이 방치되어 있다는 사실을 알게 되었다. 놀이공원 건설을 위해서는 가로로 K km, 세로로 K km인 정사각형 모양의 영역이 필요한데, 당연히 놀이공원 건설을 위해서는 해당 영역의 폐기물들을 모두 처리해야만 한다.


<N=5, K=3일 때 - 파란색 영역을 선택하면 3개를, 빨간색 영역을 선택하면 1개의 폐기물을 처리해야 한다.>


 NxN 격자 모양의 공터에서 KxK 정사각형 크기의 땅을 구매하려고 할 때, 구매할 땅에 포함 된 폐기물의 수를 최소로 할 수 있는 영역을 찾을 수 있는 프로그램을 작성해주자.


입력 형식

 첫 줄에는 테스트케이스의 수를 나타내는 1이상 100이하의 자연수 T가 주어진다.

각 테스트케이스의 첫 줄에는 두 자연수 공터의 크기를 나타내는 N과 구매할 땅의 크기를 나타내는 K가 주어진다.

  • N은 1이상 100이하의 자연수이다.
  • K는 1이상 10이하의 자연수이다. K는 N보다 작거나 같은 값을 가진다.

이후 N줄에 걸쳐서 공터의 각 행의 정보가 차례로 주어진다.

  • 각 줄은 공백으로 구분 된 0과 1이 총 N개 주어진다.
  • 0은 비어있는 땅을 나타내며, 1은 폐기물이 존재하는 칸을 나타낸다.


출력 형식

 각 테스트케이스에 대하여 KxK 모양의 땅을 구매했을 때 얻을 수 있는 최소의 폐기물의 수를 공백없이 한 줄에 출력한다.


문제 출처


Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
1
53
10010
01001
00010
00000
00100
Output
1
⋇ Please keep the input and output formats carefully
Q&A
누구나 질문하고 답변할 수 있는 Q&A 게시판입니다. 문제를 풀며 어려웠던 부분에 대해 질문해보세요.
Registered Questions (0)