시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 386 103 76 29.344%

문제

상근이는 자기가 살 집을 설계하려고 한다.

먼저, 정수 좌표마다 점이 찍혀 있는 매우 큰 종이가 필요하다. 그 다음, 이 종이의 원점에 연필을 올린다. 이제 연필을 빠르게 N번 움직여 평면도를 그린다. 연필은 절대로 종이에서 떼지 않는다. 또, 상근이는 연필을 현재 있는 점과 인접한 8개 점 중 하나로만 이동할 수 있다. (가로, 세로, 대각선) 가능한 이동은 아래 그림과 같으며, 숫자로 나타낼 수 있다.

상근이가 그린 평면도가 주어진다. 이때, 방의 수를 구하는 프로그램을 작성하시오. 방은 평면도 상에서 빈 공간이며, 연필 선으로 모든 면이 둘러 쌓여 있어야 한다. 방은 다른 방으로 둘러 쌓여질 수도 있다. 상근이는 이미 그었던 선을 또 그릴 수도 있다.

입력

첫째 줄에 연필을 움직인 횟수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에는 연필을 움직인 순서가 주어진다. 이 순서는 길이가 N인 숫자이며 0부터 7까지로 이루어져 있다. 

출력

첫째 줄에 평면도의 방의 개수를 출력한다. 

예제 입력 1

5
27250

예제 출력 1

3

예제 입력 2

9
114466173

예제 출력 2

1

예제 입력 3

19
6664442220001655360

예제 출력 3

3

W3sicHJvYmxlbV9pZCI6IjMxMzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzYzlcdWJhNzRcdWIzYzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3OTBcdWFlMzBcdWFjMDAgXHVjMGI0IFx1YzlkMVx1Yzc0NCBcdWMxMjRcdWFjYzRcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIFx1YzgxNVx1YzIxOCBcdWM4OGNcdWQ0NWNcdWI5YzhcdWIyZTQgXHVjODEwXHVjNzc0IFx1Y2MwZFx1ZDYwMCBcdWM3ODhcdWIyOTQgXHViOWU0XHVjNmIwIFx1ZDA3MCBcdWM4ODVcdWM3NzRcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWM3NzQgXHVjODg1XHVjNzc0XHVjNzU4IFx1YzZkMFx1YzgxMFx1YzVkMCBcdWM1ZjBcdWQ1NDRcdWM3NDQgXHVjNjJjXHViOWIwXHViMmU0LiBcdWM3NzRcdWM4MWMgXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YmU2MFx1Yjk3NFx1YWM4YyBOXHViYzg4IFx1YzZjMFx1YzljMVx1YzVlYyBcdWQzYzlcdWJhNzRcdWIzYzRcdWI5N2MgXHVhZGY4XHViOWIwXHViMmU0LiBcdWM1ZjBcdWQ1NDRcdWM3NDAgXHVjODA4XHViMzAwXHViODVjIFx1Yzg4NVx1Yzc3NFx1YzVkMFx1YzExYyBcdWI1YmNcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWI2MTAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1ZjBcdWQ1NDRcdWM3NDQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIDhcdWFjMWMgXHVjODEwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIChcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YywgXHViMzAwXHVhYzAxXHVjMTIwKSBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzc0XHViM2Q5XHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzNjXHViYTcwLCBcdWMyMmJcdWM3OTBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMDg5MGY4MDUtOTQ5MS00NzgxLTk2NGYtOGUwMTM4NjRiYWU3XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMDlweDsgaGVpZ2h0OiAyMTZweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YWRmOFx1YjliMCBcdWQzYzlcdWJhNzRcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmMyOVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YmMyOVx1Yzc0MCBcdWQzYzlcdWJhNzRcdWIzYzQgXHVjMGMxXHVjNWQwXHVjMTFjIFx1YmU0OCBcdWFjZjVcdWFjMDRcdWM3NzRcdWJhNzAsIFx1YzVmMFx1ZDU0NCBcdWMxMjBcdWM3M2NcdWI4NWMgXHViYWE4XHViNGUwIFx1YmE3NFx1Yzc3NCBcdWI0NThcdWI3ZWMgXHVjMzEzXHVjNWVjIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YmMyOVx1Yzc0MCBcdWIyZTRcdWI5NzggXHViYzI5XHVjNzNjXHViODVjIFx1YjQ1OFx1YjdlYyBcdWMzMTNcdWM1ZWNcdWM5YzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NFx1YmJmOCBcdWFkZjhcdWM1YzhcdWIzNTggXHVjMTIwXHVjNzQ0IFx1YjYxMCBcdWFkZjhcdWI5YjQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3OCBcdWQ2OWZcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjFjXHVjMTFjXHViMjk0IFx1YWUzOFx1Yzc3NFx1YWMwMCBOXHVjNzc4IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YmE3MCAwXHViZDgwXHVkMTMwIDdcdWFlNGNcdWM5YzBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDNjOVx1YmE3NFx1YjNjNFx1Yzc1OCBcdWJjMjlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8zIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9iN2Q5OTYzMi1kMmEwLTQ2ZDktYjMxNy1mOTk3MTZiYTU0NWZcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDIwOXB4OyBoZWlnaHQ6IDIxNnB4O1wiIFwvPjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMxMzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBUkhJVEVLVCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGFyY2hpdGVjdCBNaXJrbyBoYXMgZ2l2ZW4gaGlzIHRocmVlLXllYXIgb2xkIHNvbiwgTWlya28sIEpyLiwgdGhlIHRhc2sgb2YgY3JlYXRpbmcgdGhlIGZsb29yIHBsYW4gZm9yIHRoZSBidWlsZGluZyBoZSBpcyBjdXJyZW50bHkgd29ya2luZyBvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHN1cmZhY2UgaGUgd2lsbCBiZSB3b3JraW5nIG9uIGlzIGEgaHVnZSBwaWVjZSBvZiBwYXBlciBtb2RlbGVkIGJ5IGEgY29vcmRpbmF0ZSBwbGFuZSwgb24gd2hpY2ggYWxsIHBvaW50cyB3aXRoIGludGVnZXIgY29vcmRpbmF0ZXMgYXJlIG1hcmtlZC4gTWlya28sIEpyLiBkcmF3cyB0aGUgZmxvb3IgcGxhbiBieSBwdXR0aW5nIGhpcyBwZW5jaWwgaW4gdGhlIG9yaWdpbiBhbmQgbWFraW5nIE4gZmFzdCBhbmQgY2x1bXN5IHN0cm9rZXMuIEluIGVhY2ggc3Ryb2tlLCBoZSBtb3ZlcyB0aGUgcGVuY2lsICh3aXRob3V0IGxpZnRpbmcgaXQgb2ZmIHRoZSBzdXJmYWNlKSBzdHJhaWdodCB0byBvbmUgb2YgdGhlIDggbmVpZ2hib3VyaW5nIHBvaW50cyAoaG9yaXpvbnRhbGx5LCB2ZXJ0aWNhbGx5IG9yIGRpYWdvbmFsbHkpLiBUaGUgcG9zc2libGUgc3Ryb2tlcyBhcmUgbnVtYmVyZWQgMCB0byA3IGFzIHNob3duIGluIHRoZSBpbWFnZSBiZWxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8wODkwZjgwNS05NDkxLTQ3ODEtOTY0Zi04ZTAxMzg2NGJhZTdcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDIwOXB4OyBoZWlnaHQ6IDIxNnB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5UaGUgOCBwb3NzaWJsZSBtb3Zlcy48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgc2V2ZXJhbCB0aG91c2FuZCBzdHJva2VzLCBNaXJrbywgSnIuIGZpbmFsbHkgZ2V0cyB0aXJlZCBhZnRlciB3aGljaCBoaXMgZmF0aGVyIGF0dGVtcHRzIHRvIGNvdW50IHRoZSBudW1iZXIgb2Ygcm9vbXMgaW4gdGhlIGZsb29yIHBsYW4uIEEgcm9vbSBpcyBhbiBlbXB0eSBzcGFjZSBpbiB0aGUgZmxvb3IgcGxhbiwgc3Vycm91bmRlZCBieSBwZW5jaWwgc3Ryb2tlcyBvbiBhbGwgc2lkZXMuIE5vdGUgdGhhdCBpdCBpcyBwb3NzaWJsZSBmb3Igcm9vbXMgdG8gaGF2ZSAmcXVvdDtob2xlcyZxdW90OyBpLmUuIHRvIGNvbXBsZXRlbHkgc3Vycm91bmQgb3RoZXIgcm9vbXMuIEFsc28sIGl0IGlzIHBvc3NpYmxlIGZvciB0aGF0IE1pcmtvLCBKci4gZHJhd3MgdGhlIHNhbWUgd2FsbCBzZWdtZW50IG1vcmUgdGhhbiBvbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gdGhlIGV4YWN0IHBlbmNpbCBzdHJva2VzLCBjYWxjdWxhdGVzIHRoZSBudW1iZXIgb2Ygcm9vbXMgaW4gdGhlIGZsb29yIHBsYW4uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMDAwKSwgdGhlIG51bWJlciBvZiBwZW5jaWwgc3Ryb2tlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGEgc3RyaW5nIG9mIE4gZGlnaXRzIGJldHdlZW4gMCBhbmQgNywgdGhlIHBlbmNpbCBzdHJva2VzIGluIG9yZGVyIGluIHdoaWNoIE1pcmtvLCBKci4gbWFrZXMgdGhlbS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiByb29tcyBpbiB0aGUgZmxvb3IgcGxhbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMyI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYjdkOTk2MzItZDJhMC00NmQ5LWIzMTctZjk5NzE2YmE1NDVmXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMDlweDsgaGVpZ2h0OiAyMTZweDtcIiBcLz48XC9wPlxyXG4ifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2008 > Final Exam #2 1번