시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB196285762342.966%

문제

당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색에서 흰색으로, 혹은 흰색에서 검은색으로 변할 것이다.

당신은 모든 칸이 흰색인 3x3 보드를 입력으로 주어지는 보드의 형태로 바꾸려고 한다. 보드를 회전시킬수는 없다.

Figure D.1: 예제 입력

입력

첫 줄에는 테스트 케이스의 숫자 P(0 < P ≤ 50)이 주어진다.

각각의 테스트 케이스에 대해서 세 줄에 걸쳐 한 줄에 세 글자씩이 입력으로 들어온다. "*"은 검은색을 뜻하며 "."은 흰색을 뜻한다.

출력

각각의 테스트 케이스에 대해서 흰 보드를 입력에 주어진 보드로 바꾸는 데 필요한 최소 클릭의 횟수를 구하여라.

예제 입력 1

2
*..
**.
*..
***
*..
..*

예제 출력 1

1
3
W3sicHJvYmxlbV9pZCI6IjEwNDcyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMmVkXHVjNzkwXHViNGE0XHVjOWQxXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZjlcdWMyZTBcdWM1ZDBcdWFjOGMgM3gzIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWJjZjRcdWI0ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjZTc4XHVjNzQwIFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWQ3NzBcdWMwYzkgXHVkNjM5XHVjNzQwIFx1YWM4MFx1Yzc0MFx1YzBjOVx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVjZTc4XHVjNzQ0IFx1ZDA3NFx1YjlhZFx1ZDU1Y1x1YjJlNFx1YmE3NCBcdWIyZjlcdWMyZTBcdWM3NzQgXHVkMDc0XHViOWFkXHVkNTVjIFx1Y2U3OFx1YWNmYyBcdWFkZjggXHVjZTc4XHVjNWQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWIzZDlcdWMxMWNcdWIwYThcdWJkODEgXHViMTI0IFx1Y2U3OFx1Yzc3NCAoXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0XHViYTc0KSBcdWFjODBcdWM3NDBcdWMwYzlcdWM1ZDBcdWMxMWMgXHVkNzcwXHVjMGM5XHVjNzNjXHViODVjLCBcdWQ2MzlcdWM3NDAgXHVkNzcwXHVjMGM5XHVjNWQwXHVjMTFjIFx1YWM4MFx1Yzc0MFx1YzBjOVx1YzczY1x1Yjg1YyBcdWJjYzBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc3NCBcdWQ3NzBcdWMwYzlcdWM3NzggM3gzIFx1YmNmNFx1YjRkY1x1Yjk3YyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViYzE0XHVhZmI4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViY2Y0XHViNGRjXHViOTdjIFx1ZDY4Y1x1YzgwNFx1YzJkY1x1ZDBhY1x1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9mbGlwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4M3B4OyB3aWR0aDozMzlweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+RmlndXJlIEQuMTogXHVjNjA4XHVjODFjIFx1Yzc4NVx1YjgyNTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIyYlx1Yzc5MCBQKDAgJmx0OyBQICZsZTsgNTApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YzEzOCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjMTM4IFx1YWUwMFx1Yzc5MFx1YzUyOVx1Yzc3NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiAmcXVvdDsqJnF1b3Q7XHVjNzQwIFx1YWM4MFx1Yzc0MFx1YzBjOVx1Yzc0NCBcdWI3M2JcdWQ1NThcdWJhNzAgJnF1b3Q7LiZxdW90O1x1Yzc0MCBcdWQ3NzBcdWMwYzlcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWQ3NzAgXHViY2Y0XHViNGRjXHViOTdjIFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViY2Y0XHViNGRjXHViODVjIFx1YmMxNFx1YWZiOFx1YjI5NCBcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWQwNzRcdWI5YWRcdWM3NTggXHVkNjlmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMDQ3MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZsaXAgRml2ZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhpcyBpcyBhIGxvZ2ljIHB1enpsZSBpbiB3aGljaCB5b3UgaGF2ZSBhIHNxdWFyZSBncmlkIG9mIDMmdGltZXM7MyBjZWxscy4gRWFjaCBjZWxsIGlzIGluaXRpYWxseSBlaXRoZXIgd2hpdGUgb3IgYmxhY2suIFdoZW4geW91IGNsaWNrIG9uIGEgc3F1YXJlIGl0IGZsaXBzLCBvciB0b2dnbGVzLCB0aGUgY29sb3Igb2YgdGhhdCBzcXVhcmUgYW5kIHRoZSBjb2xvcnMgb2YgaXRzIGZvdXIgaW1tZWRpYXRlIG5vcnRoLCBzb3V0aCwgZWFzdCBhbmQgd2VzdCBuZWlnaGJvcnMgdGhhdCBleGlzdCAodGhleSBkb24mcnNxdW87dCBleGlzdCBpZiB0aGV5IHdvdWxkIGJlIG91dHNpZGUgdGhlIGdyaWQpLjxcL3A+XHJcblxyXG48cD5UaGUgcHJvYmxlbSBpcyB0byBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBjZWxsIGNsaWNrcyB0byB0cmFuc2Zvcm0gYSBncmlkIG9mIGFsbCB3aGl0ZSBjZWxscyBpbnRvIHRoZSBpbnB1dCBncmlkICh3aGljaCBpcyBhbHdheXMgcG9zc2libGUpLiBZb3UgY2Fubm90IHJvdGF0ZSB0aGUgZ3JpZC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZmxpcC5wbmdcIiBzdHlsZT1cImhlaWdodDoxODNweDsgd2lkdGg6MzM5cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlIEQuMTogVGhlIHR3byBzYW1wbGUgcHJvYmxlbXM8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCB2YWx1ZSBpbiB0aGUgaW5wdXQgZmlsZSBpcyBhbiBpbnRlZ2VyIFAgKDAgJmx0OyBQICZsZTsgNTApIG9uIGEgbGluZSBieSBpdHNlbGYgZ2l2aW5nIHRoZSBudW1iZXIgb2YgcHJvYmxlbXMgdG8gc29sdmUuPFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIG9mIHRoZSBQIHByb2JsZW1zLCAzIGxpbmVzIG9mIDMgY2hhcmFjdGVycyBkZXNjcmliZSB0aGUgaW5wdXQgZ3JpZC4gVGhlIGNoYXJhY3RlcnMgaW4gdGhlIGdyaWQgZGVzY3JpcHRpb25zIGFyZSAmbHNxdW87KiZyc3F1bzsgKGZvciBibGFjaykgYW5kICZsc3F1bzsuJnJzcXVvOyAoZm9yIHdoaXRlKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBwcm9ibGVtIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyIGdpdmluZyB0aGUgbWluaW11bSBudW1iZXIgb2YgY2xpY2tzIG5lY2Vzc2FyeSB0byB0cmFuc2Zvcm0gYSBncmlkIG9mIGFsbCB3aGl0ZSBjZWxscyBpbnRvIHRoZSBwYXR0ZXJuIGdpdmVuIGluIHRoZSBpbnB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2014 D번

  • 문제를 번역한 사람: tae
  • 문제의 오타를 찾은 사람: tony0203
  • 문제를 만든 사람: Ivor Page