시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 17585 6010 3676 31.821%

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1<=R,C<=20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1

2 4
CAAB
ADCB

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjE5ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NGNcdWQzMGNcdWJjYjMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEzOFx1Yjg1YyBSXHVjZTc4LCBcdWFjMDBcdWI4NWMgQ1x1Y2U3OFx1YzczY1x1Yjg1YyBcdWI0MWMgXHVkNDVjIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWJjZjRcdWI0ZGNcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWJjZjRcdWI0ZGNcdWM3NTggXHVhYzAxIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWIzMDBcdWJiMzhcdWM3OTAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzc0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4MDFcdWQ2MDAgXHVjNzg4XHVhY2UwLCBcdWM4OGNcdWNlMjEgXHVjMGMxXHViMmU4IFx1Y2U3OCAoMVx1ZDU4OSAxXHVjNWY0KSBcdWM1ZDBcdWIyOTQgXHViOWQwXHVjNzc0IFx1YjE5M1x1YzVlYyBcdWM3ODhcdWIyZTQuPFwvcD5cclxuPHA+XHViOWQwXHVjNzQwIFx1YzBjMVx1ZDU1OFx1Yzg4Y1x1YzZiMFx1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViMTI0IFx1Y2U3OCBcdWM5MTFcdWM3NTggXHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjMGM4XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWNlNzhcdWM1ZDAgXHVjODAxXHVkNjAwIFx1Yzc4OFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDAgXHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1YzljMFx1YjA5OFx1YzYyOCBcdWJhYThcdWI0ZTAgXHVjZTc4XHVjNWQwIFx1YzgwMVx1ZDYwMCBcdWM3ODhcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzXHVhY2ZjXHViMjk0IFx1YjJlY1x1Yjc3Y1x1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVhYzE5XHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc3NCBcdWM4MDFcdWQ3OGMgXHVjZTc4XHVjNzQ0IFx1YjQ1MCBcdWJjODggXHVjOWMwXHViMGEwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuPHA+XHVjODhjXHVjZTIxIFx1YzBjMVx1YjJlOFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWMxMWMsIFx1YjlkMFx1Yzc3NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViYTg3IFx1Y2U3OFx1Yzc0NCBcdWM5YzBcdWIwYTAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViOWQwXHVjNzc0IFx1YzljMFx1YjA5OFx1YjI5NCBcdWNlNzhcdWM3NDAgXHVjODhjXHVjZTIxIFx1YzBjMVx1YjJlOFx1Yzc1OCBcdWNlNzhcdWIzYzQgXHVkM2VjXHVkNTY4XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBSXHVhY2ZjIENcdWFjMDAgXHViZTQ4XHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsdDs9UixDJmx0Oz0yMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBSXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHViY2Y0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDYwMCBcdWM3ODhcdWIyOTQgQ1x1YWMxY1x1Yzc1OCBcdWIzMDBcdWJiMzhcdWM3OTAgXHVjNTRjXHVkMzBjXHViY2IzXHViNGU0XHVjNzc0IFx1YmU0OFx1Y2U3OCBcdWM1YzZcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWQwXHVjNzc0IFx1YzljMFx1YjBhMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWNlNzggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxOTg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGV0dGVycyIsImRlc2NyaXB0aW9uIjoiPHA+QSBzaW5nbGUtcGxheWVyIGdhbWUgaXMgcGxheWVkIG9uIGEgcmVjdGFuZ3VsYXIgYm9hcmQgZGl2aWRlZCBpbiBSIHJvd3MgYW5kIEMgY29sdW1ucy4gVGhlcmUgaXMgYSBzaW5nbGUgdXBwZXJjYXNlIGxldHRlciAoQS1aKSB3cml0dGVuIGluIGV2ZXJ5IHBvc2l0aW9uIGluIHRoZSBib2FyZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QmVmb3JlIHRoZSBiZWdnaW5nIG9mIHRoZSBnYW1lIHRoZXJlIGlzIGEgZmlndXJlIGluIHRoZSB1cHBlci1sZWZ0IGNvcm5lciBvZiB0aGUgYm9hcmQgKGZpcnN0IHJvdywgZmlyc3QgY29sdW1uKS4gSW4gZXZlcnkgbW92ZSwgYSBwbGF5ZXIgY2FuIG1vdmUgdGhlIGZpZ3VyZSB0byB0aGUgb25lIG9mIHRoZSBhZGphY2VudCBwb3NpdGlvbnMgKHVwLCBkb3duLCBsZWZ0IG9yIHJpZ2h0KS4gT25seSBjb25zdHJhaW50IGlzIHRoYXQgYSBmaWd1cmUgY2Fubm90IHZpc2l0IGEgcG9zaXRpb24gbWFya2VkIHdpdGggdGhlIHNhbWUgbGV0dGVyIHR3aWNlLiBUaGUgZ29hbCBvZiB0aGUgZ2FtZSBpcyB0byBwbGF5IGFzIG1hbnkgbW92ZXMgYXMgcG9zc2libGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBtYXhpbWFsIG51bWJlciBvZiBwb3NpdGlvbnMgaW4gdGhlIGJvYXJkIHRoZSBmaWd1cmUgY2FuIHZpc2l0IGluIGEgc2luZ2xlIGdhbWUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQywgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIGJsYW5rIGNoYXJhY3RlciwgMSAmbGU7IFIsIFMgJmxlOyAyMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBSIGxpbmVzIGNvbnRhaW4gUyBjaGFyYWN0ZXJzIGVhY2guIEVhY2ggbGluZSByZXByZXNlbnRzIG9uZSByb3cgaW4gdGhlIGJvYXJkLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQgZmlsZSBzaG91bGQgY29udGFpbiB0aGUgbWF4aW1hbCBudW1iZXIgb2YgcG9zaXRpb24gaW4gdGhlIGJvYXJkIHRoZSBmaWd1cmUgY2FuIHZpc2l0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==