시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 58 21 19 35.849%

문제

안대를 껴서 화면을 못 보는 채로 게임을 빨리 깨는 것을 "blindfolded speedrun"이라고 한다.

한 어드벤쳐 게임의 blindfolded speedrun 가이드북을 작성하던 중 난관에 봉착했다. 문제가 되는 파트의 난이도 자체가 높은 것은 아니다. 장애물이 격자 형태로 놓여 있고, 왼쪽 아래에서 출발해서 오른쪽 위로 가면 되는 간단한 파트다. 심지어 이 장애물도 게임을 킬 때마다 랜덤으로 배치되는 게 아니라 위치가 고정되어 있다. 문제는 처음에 어느 방향으로 서 있는지가 랜덤이라는 것이다. 안대를 꼈으니 방향을 알 방법이 없다.

N×N 격자가 있고, 2≤N≤20이다. 몇몇 칸에는 거대한 장애물이 있어서 지나갈 수 없고, 나머지는 비어 있어서 자유롭게 지나갈 수 있다. 격자 외부도 벽으로 둘러싸여 있어서 밖으로 나갈 수 없다. 주인공은 처음에 왼쪽 아래에 있고, 어느 방향으로 서 있는지는 모르지만 위와 오른쪽 중 하나인 것은 확실하다. 주인공은 매초 "전진", "좌회전", "우회전" 중 하나만 할 수 있다. 각 행동에는 1초가 걸린다. 전진하려고 하는데 앞에 장애물이나 벽이 있으면 그 자리에 그대로 있는다.

우리는 어느 방향으로 서 있는지에 관계 없이 오른쪽 위로 도착하도록 할 수 있는 가장 짧은 배열을 작성해야 한다. 도착하면 바로 컷신이 재생되므로 도착한 뒤 다른 칸으로 이탈할 일은 없다.

입력

첫 줄에는 N이 주어진다.

그 다음 N줄에는 격자의 행을 나타내는 길이 N의 스트링이 주어진다. E는 빈 칸이고, H는 장애물이다.

왼쪽 아래와 오른쪽 위는 무조건 E고, 왼쪽 아래에서 오른쪽 위로 가는 경로가 무조건 존재한다. (안 그러면 잘못 만든 게임이다.)

출력

가이드북에 쓸 수 있는 배열의 최소 길이를 출력한다.

예제 입력 1

3
EHE
EEE
EEE

예제 출력 1

9

힌트

"전진, 우회전, 전진, 전진, 좌회전, 전진, 좌회전, 전진, 전진"의 순서를 따르면 6초 또는 9초만에 도착할 수 있다.

W3sicHJvYmxlbV9pZCI6IjE0NDUxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNTQ4XHViMzAwIFx1YjA4MCBcdWMyYTRcdWQ1M2NcdWI0ZGNcdWI3ZWNcdWIxMDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU0OFx1YjMwMFx1Yjk3YyBcdWFlZjRcdWMxMWMgXHVkNjU0XHViYTc0XHVjNzQ0IFx1YmFiYiBcdWJjZjRcdWIyOTQgXHVjYzQ0XHViODVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWJlNjhcdWI5YWMgXHVhZTY4XHViMjk0IFx1YWM4M1x1Yzc0NCAmcXVvdDtibGluZGZvbGRlZCBzcGVlZHJ1biZxdW90O1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWM1YjRcdWI0ZGNcdWJjYTRcdWNjZDAgXHVhYzhjXHVjNzg0XHVjNzU4IGJsaW5kZm9sZGVkIHNwZWVkcnVuIFx1YWMwMFx1Yzc3NFx1YjRkY1x1YmQ4MVx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWIzNTggXHVjOTExIFx1YjA5Y1x1YWQwMFx1YzVkMCBcdWJkMDlcdWNjMjlcdWQ1ODhcdWIyZTQuIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWI0MThcdWIyOTQgXHVkMzBjXHVkMmI4XHVjNzU4IFx1YjA5Y1x1Yzc3NFx1YjNjNCBcdWM3OTBcdWNjYjRcdWFjMDAgXHViMTkyXHVjNzQwIFx1YWM4M1x1Yzc0MCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc3NCBcdWFjYTlcdWM3OTAgXHVkNjE1XHVkMGRjXHViODVjIFx1YjE5M1x1YzVlYyBcdWM3ODhcdWFjZTAsIFx1YzY3Y1x1Y2FiZCBcdWM1NDRcdWI3OThcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTc0XHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3MDRcdWI4NWMgXHVhYzAwXHViYTc0IFx1YjQxOFx1YjI5NCBcdWFjMDRcdWIyZThcdWQ1NWMgXHVkMzBjXHVkMmI4XHViMmU0LiBcdWMyZWNcdWM5YzBcdWM1YjQgXHVjNzc0IFx1YzdhNVx1YzU2MFx1YmIzY1x1YjNjNCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkMGFjIFx1YjU0Y1x1YjljOFx1YjJlNCBcdWI3OWNcdWIzNjRcdWM3M2NcdWI4NWMgXHViYzMwXHVjZTU4XHViNDE4XHViMjk0IFx1YWM4YyBcdWM1NDRcdWIyYzhcdWI3N2MgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YWNlMFx1YzgxNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWNjOThcdWM3NGNcdWM1ZDAgXHVjNWI0XHViMjkwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWMxMWMgXHVjNzg4XHViMjk0XHVjOWMwXHVhYzAwIFx1Yjc5Y1x1YjM2NFx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzU0OFx1YjMwMFx1Yjk3YyBcdWFmMDhcdWM3M2NcdWIyYzggXHViYzI5XHVkNWE1XHVjNzQ0IFx1YzU0YyBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5OJnRpbWVzO04gXHVhY2E5XHVjNzkwXHVhYzAwIFx1Yzc4OFx1YWNlMCwgMiZsZTtOJmxlOzIwXHVjNzc0XHViMmU0LiBcdWJhODdcdWJhODcgXHVjZTc4XHVjNWQwXHViMjk0IFx1YWM3MFx1YjMwMFx1ZDU1YyBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NzQgXHVjNzg4XHVjNWI0XHVjMTFjIFx1YzljMFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNWM2XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzBcdWIyOTQgXHViZTQ0XHVjNWI0IFx1Yzc4OFx1YzViNFx1YzExYyBcdWM3OTBcdWM3MjBcdWI4NmRcdWFjOGMgXHVjOWMwXHViMDk4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWNhOVx1Yzc5MCBcdWM2NzhcdWJkODBcdWIzYzQgXHViY2JkXHVjNzNjXHViODVjIFx1YjQ1OFx1YjdlY1x1YzJmOFx1YzVlYyBcdWM3ODhcdWM1YjRcdWMxMWMgXHViYzE2XHVjNzNjXHViODVjIFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWM4ZmNcdWM3NzhcdWFjZjVcdWM3NDAgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzY3Y1x1Y2FiZCBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWM1YjRcdWIyOTAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzExYyBcdWM3ODhcdWIyOTRcdWM5YzBcdWIyOTQgXHViYWE4XHViOTc0XHVjOWMwXHViOWNjIFx1YzcwNFx1YzY0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3OCBcdWFjODNcdWM3NDAgXHVkNjU1XHVjMmU0XHVkNTU4XHViMmU0LiBcdWM4ZmNcdWM3NzhcdWFjZjVcdWM3NDAgXHViOWU0XHVjZDA4ICZxdW90O1x1YzgwNFx1YzljNCZxdW90OywgJnF1b3Q7XHVjODhjXHVkNjhjXHVjODA0JnF1b3Q7LCAmcXVvdDtcdWM2YjBcdWQ2OGNcdWM4MDQmcXVvdDsgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDU4OVx1YjNkOVx1YzVkMFx1YjI5NCAxXHVjZDA4XHVhYzAwIFx1YWM3OFx1YjliMFx1YjJlNC4gXHVjODA0XHVjOWM0XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWM1NWVcdWM1ZDAgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzc0XHViMDk4IFx1YmNiZFx1Yzc3NCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVhZGY4IFx1Yzc5MFx1YjlhY1x1YzVkMCBcdWFkZjhcdWIzMDBcdWI4NWMgXHVjNzg4XHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWIyOTQgXHVjNWI0XHViMjkwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWMxMWMgXHVjNzg4XHViMjk0XHVjOWMwXHVjNWQwIFx1YWQwMFx1YWNjNCBcdWM1YzZcdWM3NzQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzcwNFx1Yjg1YyBcdWIzYzRcdWNjMjlcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzllN1x1Yzc0MCBcdWJjMzBcdWM1ZjRcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViM2M0XHVjYzI5XHVkNTU4XHViYTc0IFx1YmMxNFx1Yjg1YyBcdWNlZjdcdWMyZTBcdWM3NzQgXHVjN2FjXHVjMGRkXHViNDE4XHViYmMwXHViODVjIFx1YjNjNFx1Y2MyOVx1ZDU1YyBcdWI0YTQgXHViMmU0XHViOTc4IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWQwYzhcdWQ1NjAgXHVjNzdjXHVjNzQwIFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgTlx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjYTlcdWM3OTBcdWM3NTggXHVkNTg5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWFlMzhcdWM3NzQgTlx1Yzc1OCBcdWMyYTRcdWQyYjhcdWI5YzFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBFXHViMjk0IFx1YmU0OCBcdWNlNzhcdWM3NzRcdWFjZTAsIEhcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2N2NcdWNhYmQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3MDRcdWIyOTQgXHViYjM0XHVjODcwXHVhYzc0IEVcdWFjZTAsIFx1YzY3Y1x1Y2FiZCBcdWM1NDRcdWI3OThcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzcwNFx1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1YmIzNFx1Yzg3MFx1YWM3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIChcdWM1NDggXHVhZGY4XHViN2VjXHViYTc0IFx1Yzc5OFx1YmFiYiBcdWI5Y2NcdWI0ZTAgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0Lik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWM3NzRcdWI0ZGNcdWJkODFcdWM1ZDAgXHVjNGY4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzMwXHVjNWY0XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4mcXVvdDtcdWM4MDRcdWM5YzQsIFx1YzZiMFx1ZDY4Y1x1YzgwNCwgXHVjODA0XHVjOWM0LCBcdWM4MDRcdWM5YzQsIFx1Yzg4Y1x1ZDY4Y1x1YzgwNCwgXHVjODA0XHVjOWM0LCBcdWM4OGNcdWQ2OGNcdWM4MDQsIFx1YzgwNFx1YzljNCwgXHVjODA0XHVjOWM0JnF1b3Q7XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI1MzBcdWI5NzRcdWJhNzQgNlx1Y2QwOCBcdWI2MTBcdWIyOTQgOVx1Y2QwOFx1YjljY1x1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE0NDUxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ293IE5hdmlnYXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPkJlc3NpZSBoYXMgZ290dGVuIGhlcnNlbGYgc3R1Y2sgb24gdGhlIHdyb25nIHNpZGUgb2YgRmFybWVyIEpvaG4mIzM5O3MgYmFybiBhZ2FpbiwgYW5kIHNpbmNlIGhlciB2aXNpb24gaXMgc28gcG9vciwgc2hlIG5lZWRzIHlvdXIgaGVscCBuYXZpZ2F0aW5nIGFjcm9zcyB0aGUgYmFybi48XC9wPlxyXG5cclxuPHA+VGhlIGJhcm4gaXMgZGVzY3JpYmVkIGJ5IGFuJm5ic3A7TiZ0aW1lcztOIGdyaWQgb2Ygc3F1YXJlIGNlbGxzICgyJmxlO04mbGU7MjApLCBzb21lIGJlaW5nIGVtcHR5IGFuZCBzb21lIGNvbnRhaW5pbmcgaW1wYXNzYWJsZSBoYXliYWxlcy4gQmVzc2llIHN0YXJ0cyBpbiB0aGUgbG93ZXItbGVmdCBjb3JuZXIgKGNlbGwgMSwxKSBhbmQgd2FudHMgdG8gbW92ZSB0byB0aGUgdXBwZXItcmlnaHQgY29ybmVyIChjZWxsJm5ic3A7TixOKS4gWW91IGNhbiBndWlkZSBoZXIgYnkgdGVsbGluZyBoZXIgYSBzZXF1ZW5jZSBvZiBpbnN0cnVjdGlvbnMsIGVhY2ggb2Ygd2hpY2ggaXMgZWl0aGVyICZxdW90O2ZvcndhcmQmcXVvdDssICZxdW90O3R1cm4gbGVmdCA5MCBkZWdyZWVzJnF1b3Q7LCBvciAmcXVvdDt0dXJuIHJpZ2h0IDkwIGRlZ3JlZXMmcXVvdDsuIFlvdSB3YW50IHRvIGlzc3VlIHRoZSBzaG9ydGVzdCBzZXF1ZW5jZSBvZiBpbnN0cnVjdGlvbnMgdGhhdCB3aWxsIGd1aWRlIGhlciB0byBoZXIgZGVzdGluYXRpb24uIElmIHlvdSBpbnN0cnVjdCBCZXNzaWUgdG8gbW92ZSBvZmYgdGhlIGdyaWQgKGkuZS4sIGludG8gdGhlIGJhcm4gd2FsbCkgb3IgaW50byBhIGhheWJhbGUsIHNoZSB3aWxsIG5vdCBtb3ZlIGFuZCB3aWxsIHNraXAgdG8gdGhlIG5leHQgY29tbWFuZCBpbiB5b3VyIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCBCZXNzaWUgZG9lc24mIzM5O3Qga25vdyBpZiBzaGUgc3RhcnRzIG91dCBmYWNpbmcgdXAgKHRvd2FyZHMgY2VsbCAxLDIpIG9yIHJpZ2h0ICh0b3dhcmRzIGNlbGwgMiwxKS4gWW91IG5lZWQgdG8gZ2l2ZSB0aGUgc2hvcnRlc3Qgc2VxdWVuY2Ugb2YgZGlyZWN0aW9ucyB0aGF0IHdpbGwgZ3VpZGUgaGVyIHRvIHRoZSBnb2FsIHJlZ2FyZGxlc3Mgb2Ygd2hpY2ggY2FzZSBpcyB0cnVlLiBPbmNlIHNoZSByZWFjaGVzIHRoZSBnb2FsIHNoZSB3aWxsIGlnbm9yZSBmdXJ0aGVyIGNvbW1hbmRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMmbmJzcDtOLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSZuYnNwO04mbmJzcDtmb2xsb3dpbmcgbGluZXMgY29udGFpbnMgYSBzdHJpbmcgb2YgZXhhY3RseSZuYnNwO04mbmJzcDtjaGFyYWN0ZXJzLCByZXByZXNlbnRpbmcgdGhlIGJhcm4uIFRoZSBmaXJzdCBjaGFyYWN0ZXIgb2YgdGhlIGxhc3QgbGluZSBpcyBjZWxsIDEsMS4gVGhlIGxhc3QgY2hhcmFjdGVyIG9mIHRoZSBmaXJzdCBsaW5lIGlzIGNlbGwgTiwgTi48XC9wPlxyXG5cclxuPHA+RWFjaCBjaGFyYWN0ZXIgd2lsbCBlaXRoZXIgYmUgYW4gSCB0byByZXByZXNlbnQgYSBoYXliYWxlIG9yIGFuIEUgdG8gcmVwcmVzZW50IGFuIGVtcHR5IHNxdWFyZS48XC9wPlxyXG5cclxuPHA+SXQgaXMgZ3VhcmFudGVlZCB0aGF0IGNlbGxzIDEsMSBhbmQmbmJzcDtOLE4gd2lsbCBiZSBlbXB0eSwgYW5kIGZ1cnRoZXJtb3JlIGl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGVyZSBpcyBhIHBhdGggb2YgZW1wdHkgc3F1YXJlcyBmcm9tIGNlbGwgMSwxIHRvIGNlbGwmbmJzcDtOLE4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gYSBzaW5nbGUgbGluZSBvZiBvdXRwdXQsIG91dHB1dCB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBzZXF1ZW5jZSBvZiBkaXJlY3Rpb25zIHRoYXQgd2lsbCBndWlkZSBCZXNzaWUgdG8gdGhlIGdvYWwsIGlycmVzcGVjdGl2ZSB3aGV0aGVyIHNoZSBzdGFydHMgZmFjaW5nIHVwIG9yIHJpZ2h0LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhpcyBleGFtcGxlLCB0aGUgaW5zdHJ1Y3Rpb25zICZxdW90O0ZvcndhcmQsIFJpZ2h0LCBGb3J3YXJkLCBGb3J3YXJkLCBMZWZ0LCBGb3J3YXJkLCBMZWZ0LCBGb3J3YXJkLCBGb3J3YXJkJnF1b3Q7IHdpbGwgZ3VpZGUgQmVzc2llIHRvIHRoZSBkZXN0aW5hdGlvbiBpcnJlc3BlY3RpdmUgb2YgaGVyIHN0YXJ0aW5nIG9yaWVudGF0aW9uLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==