시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 256 MB3248107362129.813%

문제

음수가 아닌 정수들의 격자가 주어진다. 당신은 이 격자에 다음 연산을 행할 수 있다.

  • 1. 격자에서 가로 또는 세로로 인접한 정수 2개를 고른다.
  • 2. 각 정수가 양수일 때 1 감소시킨다.

다음 그림은 총 4개의 연속한 연산을 2*2 격자에 가해서 모든 정수를 0으로 만든 과정을 보여준다.

위 예제에서는 모든 정수를 0으로 만들기 위해 4번의 연산을 행했다. 이보다 적은 횟수의 연산으로는 모든 정수를 0으로 만들 수 없다는 것을 쉽게 알 수 있다.

격자가 주어졌을 때 모든 정수를 0으로 만들기 위해 필요한 최소 연산의 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 격자의 해당 행에 있는 m개의 정수가 열 순서대로 주어진다. 각 정수는 0 이상 1,000 이하이다.

출력

각 테스트 케이스마다 필요한 연산의 최소 횟수를 한 줄에 출력한다.

예제 입력 1

2
2 2
1 3
1 2
2 4
2 3 2 3
1 2 1 1

예제 출력 1

4
8
W3sicHJvYmxlbV9pZCI6IjExNDk1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2E5XHVjNzkwIDAgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NGNcdWMyMThcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1YjRlNFx1Yzc1OCBcdWFjYTlcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NDAgXHVjNzc0IFx1YWNhOVx1Yzc5MFx1YzVkMCBcdWIyZTRcdWM3NGMgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEuIFx1YWNhOVx1Yzc5MFx1YzVkMFx1YzExYyBcdWFjMDBcdWI4NWMgXHViNjEwXHViMjk0IFx1YzEzOFx1Yjg1Y1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjODE1XHVjMjE4IDJcdWFjMWNcdWI5N2MgXHVhY2UwXHViOTc4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4yLiBcdWFjMDEgXHVjODE1XHVjMjE4XHVhYzAwIFx1YzU5MVx1YzIxOFx1Yzc3YyBcdWI1NGMgMSBcdWFjMTBcdWMxOGNcdWMyZGNcdWQwYThcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YWRmOFx1YjliY1x1Yzc0MCBcdWNkMWQgNFx1YWMxY1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzQ0IDIqMiBcdWFjYTlcdWM3OTBcdWM1ZDAgXHVhYzAwXHVkNTc0XHVjMTFjIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMyMThcdWI5N2MgMFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTAgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YmNmNFx1YzVlY1x1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTE0OTVcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjhweDsgd2lkdGg6NDEycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzA0IFx1YzYwOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4XHViOTdjIDBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCA0XHViYzg4XHVjNzU4IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWQ1ODlcdWQ1ODhcdWIyZTQuIFx1Yzc3NFx1YmNmNFx1YjJlNCBcdWM4MDFcdWM3NDAgXHVkNjlmXHVjMjE4XHVjNzU4IFx1YzVmMFx1YzBiMFx1YzczY1x1Yjg1Y1x1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4XHViOTdjIDBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzI3ZFx1YWM4YyBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2E5XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHViYWE4XHViNGUwIFx1YzgxNVx1YzIxOFx1Yjk3YyAwXHVjNzNjXHViODVjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVkNjlmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVhY2ZjIG0gKDIgJmxlOyBuLCBtICZsZTsgNTApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgblx1Yzc0MCBcdWFjYTlcdWM3OTBcdWM3NTggXHVkNTg5IFx1YWMxY1x1YzIxOCwgbVx1Yzc0MCBcdWFjYTlcdWM3OTBcdWM3NTggXHVjNWY0IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxIFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWQ1NzRcdWIyZjkgXHVkNTg5XHVjNWQwIFx1Yzc4OFx1YjI5NCBtXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM1ZjQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzgxNVx1YzIxOFx1YjI5NCAwIFx1Yzc3NFx1YzBjMSAxLDAwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjExNDk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR3JpZCIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhIGdyaWQgb2Ygbm9ubmVnYXRpdmUgaW50ZWdlcnMuIFRoZXJlIGlzIGFuIG9wZXJhdGlvbiB0aGF0IHBlcmZvcm1zIHRoZSBmb2xsb3dpbmcgdHdvIHN0ZXBzIG9uIHRoZSBncmlkOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlN0ZXAgMS4gSXQgY2hvb3NlcyB0d28gbnVtYmVycyBhZGphY2VudCB2ZXJ0aWNhbGx5IG9yIGhvcml6b250YWxseSBpbiB0aGUgZ3JpZC48XC9saT5cclxuXHQ8bGk+U3RlcCAyLiBJdCBkZWNyZWFzZXMgZWFjaCBudW1iZXIgY2hvc2VuIGluIFN0ZXAgMSBieSAxIGlmIGl0IGlzIHBvc2l0aXZlLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBGaWd1cmUgMSBzaG93cyB0aGUgcmVzdWx0IG9mIGZvdXIgc3VjY2Vzc2l2ZSBleGVjdXRpb25zIG9mIHRoZSBvcGVyYXRpb24gb24gYSAyLWJ5LTIgZ3JpZCBvZiBmb3VyIG51bWJlcnMuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMTQ5NVwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDo2OHB4OyB3aWR0aDo0MTJweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+RmlndXJlIDEuIEZvdXIgc3VjY2Vzc2l2ZSBleGVjdXRpb25zIG9mIHRoZSBvcGVyYXRpb24gb24gYSAyLWJ5LTIgZ3JpZCBvZiBmb3VyIG51bWJlcnM8XC9wPlxyXG5cclxuPHA+SW4gdGhlIGFib3ZlIGV4YW1wbGUsIHRoZSBvcGVyYXRpb24gd2FzIGV4ZWN1dGVkIGZvdXIgdGltZXMgdG8gbWFrZSBhbGwgdGhlIG51bWJlcnMgaW4gdGhlIGluaXRpYWwgZ3JpZCB0byAwLiBZb3UgY2FuIGVhc2lseSBjaGVjayB0aGVyZSBpcyBubyB3YXkgdG8gZG8gc28gdXNpbmcgbGVzcyBudW1iZXIgb2YgZXhlY3V0aW9ucyBvZiB0aGUgb3BlcmF0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGV4ZWN1dGlvbnMgb2YgdGhlIG9wZXJhdGlvbiB0byBtYWtlIGFsbCB0aGUgbnVtYmVycyBpbiB0aGUgZ3JpZCB0byAwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMsIG4gYW5kIG0gKDIgJmxlOyBuLCBtICZsZTsgNTApLCB3aGVyZSBuIGlzIHRoZSByb3cgc2l6ZSBhbmQgbSBpcyB0aGUgY29sdW1uIHNpemUgb2YgYSBncmlkLiBJbiB0aGUgZm9sbG93aW5nIG4gbGluZXMsIHRoZSBlbGVtZW50cyBvZiB0aGUgZ3JpZCBhcmUgZ2l2ZW4gcm93IGJ5IHJvdywgdGhhdCBpcywgdGhlIGktdGggbGluZSBjb250YWlucyBtIGludGVnZXJzIHdoaWNoIGNvcnJlc3BvbmQgdG8gdGhlIGVsZW1lbnRzIG9mIHRoZSBpLXRoIHJvdyBvZiB0aGUgZ3JpZCBpbiBvcmRlciwgZm9yIDEgJmxlOyBpICZsZTsgbi4gRWFjaCBpbnRlZ2VyIGluIHRoZSBncmlkIGlzIGJldHdlZW4gMCBhbmQgMSwwMDAsIGluY2x1c2l2ZWx5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhbiBpbnRlZ2VyIHJlcHJlc2VudGluZyB0aGUgbWluaW11bSBudW1iZXIgb2YgZXhlY3V0aW9ucyBvZiB0aGUgb3BlcmF0aW9ucyByZXF1aXJlZCBpbiB0aGUgcHJvYmxlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2015 C번

  • 문제를 번역한 사람: kks227