시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 466 181 145 40.503%

문제

N-Queen 문제를 풀어본 일이 있을 것이다. 격자판에 N개의 Queen을 배치하되, 각 Queen이 서로를 공격할 수 없게 배치하려면 N은 최대 얼마까지 가능한지를 알아내는 문제이다.

이번에는 Rook을 가지고 같은 문제를 풀어 보자. Rook은 격자판의 같은 열, 혹은 같은 행에 다른 말이 있을 경우, 그 말을 공격할 수 있는 말이다.

다만, 이 경우에 문제가 그 가치를 확보하기 위해서는, 격자판을 약간 변형해야 한다. 격자판에 벽과 구덩이를 도입하자.

벽을 사이에 두고 있는 두 Rook은, 서로 볼 수 없으므로, 서로 공격할 수가 없다. 물론 벽이 놓여 있는 격자에는 Rook을 놓을 수 없다.

반면, 구덩이를 사이에 두고 있는 두 Rook은 서로 공격을 시도한다. (아마 공격 도중에 구덩이에 빠지겠지만.) 따라서 두 Rook이 구덩이를 사이에 두고 마주보도록 배치해서는 안 된다. 또, 구덩이를 파 놓은 격자에도 Rook을 놓을 수 없다.

격자판의 모양이 주어졌을 때, Rook을 가장 많이 배치하기 위한 방법을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 격자의 크기를 나타내는 두 자연수 M, N이 주어진다. 격자가 M행 N열로 이루어져 있다는 의미이다. (1<=M, N<=100) 둘째 줄부터는 격자의 모양을 나타내는 정보가 한 줄에 한 행씩 주어진다. 0은 빈 격자, 1은 구덩이가 파인 격자, 2는 벽이 놓인 격자를 의미한다.

출력

첫째 줄에, 배치할 수 있는 Rook의 최대 개수를 출력한다.

예제 입력 1

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

예제 출력 1

2

힌트

1행 2열과 3행 3열에 하나씩, 총 두 개의 Rook을 배치할 수 있다.

W3sicHJvYmxlbV9pZCI6IjE3NjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOLVJvb2siLCJkZXNjcmlwdGlvbiI6IjxwPk4tUXVlZW4gXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MFx1YzViNFx1YmNmOCBcdWM3N2NcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVhY2E5XHVjNzkwXHVkMzEwXHVjNWQwIE5cdWFjMWNcdWM3NTggUXVlZW5cdWM3NDQgXHViYzMwXHVjZTU4XHVkNTU4XHViNDE4LCBcdWFjMDEgUXVlZW5cdWM3NzQgXHVjMTFjXHViODVjXHViOTdjIFx1YWNmNVx1YWNhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhYzhjIFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjgyNFx1YmE3NCBOXHVjNzQwIFx1Y2Q1Y1x1YjMwMCBcdWM1YmNcdWI5YzhcdWFlNGNcdWM5YzAgXHVhYzAwXHViMmE1XHVkNTVjXHVjOWMwXHViOTdjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YmM4OFx1YzVkMFx1YjI5NCBSb29rXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWFjMTlcdWM3NDAgXHViYjM4XHVjODFjXHViOTdjIFx1ZDQ4MFx1YzViNCBcdWJjZjRcdWM3OTAuIFJvb2tcdWM3NDAgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNzU4IFx1YWMxOVx1Yzc0MCBcdWM1ZjQsIFx1ZDYzOVx1Yzc0MCBcdWFjMTlcdWM3NDAgXHVkNTg5XHVjNWQwIFx1YjJlNFx1Yjk3OCBcdWI5ZDBcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YWNiZFx1YzZiMCwgXHVhZGY4IFx1YjlkMFx1Yzc0NCBcdWFjZjVcdWFjYTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWI5ZDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1YjljYywgXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWJiMzhcdWM4MWNcdWFjMDAgXHVhZGY4IFx1YWMwMFx1Y2U1OFx1Yjk3YyBcdWQ2NTVcdWJjZjRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0LCBcdWFjYTlcdWM3OTBcdWQzMTBcdWM3NDQgXHVjNTdkXHVhYzA0IFx1YmNjMFx1ZDYxNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWNhOVx1Yzc5MFx1ZDMxMFx1YzVkMCZuYnNwO1x1YmNiZFx1YWNmYyBcdWFkNmNcdWIzNjlcdWM3NzRcdWI5N2MgXHViM2M0XHVjNzg1XHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWJjYmRcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViNDUwIFJvb2tcdWM3NDAsIFx1YzExY1x1Yjg1YyBcdWJjZmMgXHVjMjE4IFx1YzVjNlx1YzczY1x1YmJjMFx1Yjg1YywgXHVjMTFjXHViODVjIFx1YWNmNVx1YWNhOVx1ZDU2MCBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0LiBcdWJiM2NcdWI4NjAgXHViY2JkXHVjNzc0IFx1YjE5M1x1YzVlYyBcdWM3ODhcdWIyOTQgXHVhY2E5XHVjNzkwXHVjNWQwXHViMjk0IFJvb2tcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMxOFx1YmE3NCwgXHVhZDZjXHViMzY5XHVjNzc0XHViOTdjIFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjQ1MCBSb29rXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWFjZjVcdWFjYTlcdWM3NDQgXHVjMmRjXHViM2M0XHVkNTVjXHViMmU0LiAoXHVjNTQ0XHViOWM4IFx1YWNmNVx1YWNhOSBcdWIzYzRcdWM5MTFcdWM1ZDAgXHVhZDZjXHViMzY5XHVjNzc0XHVjNWQwIFx1YmU2MFx1YzljMFx1YWNhMFx1YzljMFx1YjljYy4pIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWI0NTAgUm9va1x1Yzc3NCBcdWFkNmNcdWIzNjlcdWM3NzRcdWI5N2MgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWI5YzhcdWM4ZmNcdWJjZjRcdWIzYzRcdWI4NWQgXHViYzMwXHVjZTU4XHVkNTc0XHVjMTFjXHViMjk0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1YjYxMCwgXHVhZDZjXHViMzY5XHVjNzc0XHViOTdjIFx1ZDMwYyBcdWIxOTNcdWM3NDAgXHVhY2E5XHVjNzkwXHVjNWQwXHViM2M0IFJvb2tcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc1OCBcdWJhYThcdWM1OTFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgUm9va1x1Yzc0NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYTlcdWM3OTBcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4IE0sIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjYTlcdWM3OTBcdWFjMDAgTVx1ZDU4OSBOXHVjNWY0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiAoMSZsdDs9TSwgTiZsdDs9MTAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWJhYThcdWM1OTFcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1YyBcdWQ1ODlcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAwXHVjNzQwIFx1YmU0OCBcdWFjYTlcdWM3OTAsIDFcdWM3NDAgXHVhZDZjXHViMzY5XHVjNzc0XHVhYzAwIFx1ZDMwY1x1Yzc3OCBcdWFjYTlcdWM3OTAsIDJcdWIyOTQgXHViY2JkXHVjNzc0IFx1YjE5M1x1Yzc3OCBcdWFjYTlcdWM3OTBcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFJvb2tcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjFcdWQ1ODkgMlx1YzVmNFx1YWNmYyAzXHVkNTg5IDNcdWM1ZjRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5LCBcdWNkMWQgXHViNDUwIFx1YWMxY1x1Yzc1OCBSb29rXHVjNzQ0IFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTc2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJveWFsIGd1YXJkcyIsImRlc2NyaXB0aW9uIjoiPHA+T25jZSB1cG9uIGEgdGltZSwgdGhlcmUgd2FzIGEga2luZ2RvbS4gSXQgaGFkIGV2ZXJ5dGhpbmcgYSBraW5nZG9tIG5lZWRzLCBuYW1lbHkgYSBraW5nIGFuZCBoaXMgY2FzdGxlLiBUaGUgZ3JvdW5kLXBsYW4gb2YgdGhlIGNhc3RsZSB3YXMgYSByZWN0YW5nbGUgdGhhdCB3YXMgZGl2aWRlZCBpbnRvIE0mdGltZXM7TiB1bml0IHNxdWFyZXMuIFNvbWUgb2YgdGhlIHNxdWFyZXMgYXJlIHdhbGxzLCBzb21lIG9mIHRoZW0gYXJlIGZyZWUuIFdlIHdpbGwgY2FsbCBlYWNoIG9mIHRoZSBmcmVlIHNxdWFyZXMgYSByb29tLiBUaGUga2luZyBvZiBvdXIga2luZ2RvbSB3YXMgZXh0cmVtZWx5IHBhcmFub2lkLCBzbyBvbmUgZGF5IGhlIGRlY2lkZWQgdG8gbWFrZSBoaWRkZW4gcGl0cyAod2l0aCBhbGxpZ2F0b3JzIGF0IHRoZSBib3R0b20pIGluIHNvbWUgb2YgdGhlIHJvb21zLjxcL3A+XHJcblxyXG48cD5CdXQgdGhpcyB3YXMgc3RpbGwgbm90IGVub3VnaC4gT25lIHdlZWsgbGF0ZXIsIGhlIGRlY2lkZWQgdG8gcGxhY2UgYXMgbWFueSBndWFyZHMgYXMgcG9zc2libGUgaW5zaWRlIGhpcyBjYXN0bGUuIEhvd2V2ZXIsIHRoaXMgd29uJiMzOTt0IGJlIHNvIHNpbXBsZS4gVGhlIGd1YXJkcyBhcmUgdHJhaW5lZCBzbyB0aGF0IGltbWVkaWF0ZWx5IGFmdGVyIHRoZXkgc2VlIHNvbWVvbmUsIHRoZXkgc2hvb3QgYXQgaGltLiBBbmQgc28gdGhlIGtpbmcgaGFzIHRvIHBsYWNlIHRoZSBndWFyZHMgY2FyZWZ1bGx5LCBiZWNhdXNlIGlmIHR3byBndWFyZHMgd291bGQgc2VlIGVhY2ggb3RoZXIsIHRoZXkgd291bGQgc2hvb3QgYXQgdGhlbXNlbHZlcyEgQWxzbyBldmlkZW50bHkgdGhlIGtpbmcgY2FuJiMzOTt0IHBsYWNlIGEgZ3VhcmQgaW50byBhIHJvb20gd2l0aCBhIHBpdC48XC9wPlxyXG5cclxuPHA+VHdvIGd1YXJkcyBpbiBhIHJvb20gc2VlIGVhY2ggb3RoZXIsIHNvIGVhY2ggcm9vbSBtYXkgY29udGFpbiBhdCBtb3N0IG9uZSBndWFyZC4gVHdvIGd1YXJkcyBpbiBkaWZmZXJlbnQgcm9vbXMgc2VlIGVhY2ggb3RoZXIgaWYgYW5kIG9ubHkgaWYgdGhlIHNxdWFyZXMgY29ycmVzcG9uZGluZyB0byB0aGVpciByb29tcyBhcmUgaW4gdGhlIHNhbWUgcm93IG9yIGluIHRoZSBzYW1lIGNvbHVtbiBvZiB0aGUgcGxhbiBvZiB0aGUgY2FzdGxlIGFuZCB0aGVyZSBpcyBubyB3YWxsIGJldHdlZW4gdGhlbS4gKFRoZSBndWFyZCBjYW4gc2VlIG9ubHkgaW4gZm91ciBkaXJlY3Rpb25zLCBtdWNoIGxpa2UgYSByb29rIGluIGNoZXNzLik8XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGZpbmQgb3V0LCBob3cgbWFueSBndWFyZHMgY2FuIHRoZSBraW5nIHBsYWNlIGluc2lkZSBoaXMgY2FzdGxlIChhY2NvcmRpbmcgdG8gdGhlIHJ1bGVzIGFib3ZlKSBhbmQgdG8gZmluZCBvbmUgcG9zc2libGUgYXNzaWdubWVudCBvZiB0aGF0IG1hbnkgZ3VhcmRzIGludG8gdGhlIHJvb21zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgdHdvIG51bWJlcnMgTSwgTiwgMSZsdDs9TSxOJmx0Oz0yMDAgLSB0aGUgZGltZW5zaW9ucyBvZiB0aGUgZ3JvdW5kLXBsYW4gb2YgdGhlIGNhc3RsZS4gVGhlIGktdGggb2YgdGhlIGZvbGxvd2luZyBNIGxpbmVzIGNvbnRhaW5zIE4gbnVtYmVycyBhPHN1Yj5pLDE8XC9zdWI+LCAuLi4sIGE8c3ViPmksTjxcL3N1Yj4sIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLCB3aGVyZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5hPHN1Yj5pLGo8XC9zdWI+PTAgbWVhbnMgdGhhdCB0aGUgc3F1YXJlIGlzIGZyZWUgKGEgcm9vbSB3aXRob3V0IGEgcGl0KTxcL2xpPlxyXG5cdDxsaT5hPHN1Yj5pLGo8XC9zdWI+PTEgbWVhbnMgdGhhdCB0aGUgc3F1YXJlIGNvbnRhaW5zIGEgcGl0PFwvbGk+XHJcblx0PGxpPmE8c3ViPmksajxcL3N1Yj49MiBtZWFucyB0aGF0IHRoZSBzcXVhcmUgaXMgYSB3YWxsPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm90ZSB0aGF0IHRoZSBmaXJzdCBjb29yZGluYXRlIG9mIGEgc3F1YXJlIGlzIHRoZSByb3cgYW5kIHRoZSBzZWNvbmQgb25lIGlzIHRoZSBjb2x1bW4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIG91dHB1dCBmaWxlIHNob3VsZCBjb250YWluIHRoZSBtYXhpbXVtIG51bWJlciBLIG9mIGd1YXJkcyB0aGUga2luZyBtYXkgcGxhY2UgaW5zaWRlIGhpcyBjYXN0bGUuIFRoZSBmb2xsb3dpbmcgSyBsaW5lcyBzaG91bGQgY29udGFpbiBvbmUgcG9zc2libGUgYXNzaWdubWVudCBvZiBLIGd1YXJkcyBpbnRvIHRoZSBmcmVlIHJvb21zIG9mIHRoZSBjYXN0bGUgc28gdGhhdCBubyB0d28gZ3VhcmRzIHdvdWxkIHNlZSBlYWNoIG90aGVyLjxcL3A+XHJcblxyXG48cD5Nb3JlIHByZWNpc2VseSwgdGhlIGktdGggb2YgdGhlc2UgbGluZXMgc2hvdWxkIGNvbnRhaW4gdHdvIGludGVnZXJzIHI8c3ViPmk8XC9zdWI+LCBjPHN1Yj5pPFwvc3ViPiBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UgLSB0aGUgY29vcmRpbmF0ZXMgb2YgdGhlIHJvb20gd2hlcmUgaS10aCBndWFyZCB3aWxsIGJlIHBsYWNlZCAocjxzdWI+aTxcL3N1Yj4gaXMgdGhlIHJvdyBhbmQgYzxzdWI+aTxcL3N1Yj4gaXMgdGhlIGNvbHVtbikuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvMjAwMi0yMi0xLmdpZlwiIHN0eWxlPVwiaGVpZ2h0Ojg3cHg7IHdpZHRoOjI4NXB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=