시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB46923020651.500%

문제

상근이와 창영이는 트리플렛이라는 게임을 하고 있다. 이 게임을 하려면 칠판에 N*N 그리드를 그려야 한다. 그 다음 알파벳 대문자를 적절히 각 칸에 써 넣는다. 한 알파벳을 여러 칸에 쓸 수는 없다.

여기까지는 게임을 하기 위해 준비하는 과정이다. 트리플렛의 목표는 직선을 이루는 세 글자를 되도록 많이 찾는 것이다. 세 글자가 직선을 이루려면, 글자가 있는 칸의 중심을 연결한 선이 선분이어야 한다.

칠판에 그린 그리드의 상태가 주어졌을 때, 직선을 이루는 세 글자(트리플렛)의 개수를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 그리드의 크기 N이 주어진다. (3 ≤ N ≤ 100)

다음 N개 줄에는 그리드에 채워져 있는 글자가 주어진다. 글자를 채우지 않은 빈 칸의 경우에는 '.'로 주어진다.

출력

첫째 줄에 트리플렛의 개수를 출력한다.

예제 입력 1

4
...D
..C.
.B..
A...

예제 출력 1

4

예제 입력 2

5
..T..
A....
.FE.R
....X
S....

예제 출력 2

3

예제 입력 3

10
....AB....
..C....D..
.E......F.
...G..H...
I........J
K........L
...M..N...
.O......P.
..Q....R..
....ST....

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjMwNDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYjhcdWI5YWNcdWQ1MGNcdWI4MWIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVkMmI4XHViOWFjXHVkNTBjXHViODFiXHVjNzc0XHViNzdjXHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWNlNjBcdWQzMTBcdWM1ZDAgTipOIFx1YWRmOFx1YjlhY1x1YjRkY1x1Yjk3YyBcdWFkZjhcdWI4MjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjMzY4IFx1YjEyM1x1YjI5NFx1YjJlNC4gXHVkNTVjIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHVjZTc4XHVjNWQwIFx1YzRmOCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWFlMzBcdWFlNGNcdWM5YzBcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjOTAwXHViZTQ0XHVkNTU4XHViMjk0IFx1YWNmY1x1YzgxNVx1Yzc3NFx1YjJlNC4gXHVkMmI4XHViOWFjXHVkNTBjXHViODFiXHVjNzU4IFx1YmFhOVx1ZDQ1Y1x1YjI5NCBcdWM5YzFcdWMxMjBcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YzEzOCBcdWFlMDBcdWM3OTBcdWI5N2MgXHViNDE4XHViM2M0XHViODVkIFx1YjljZVx1Yzc3NCBcdWNjM2VcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWMxMzggXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzljMVx1YzEyMFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWI4MjRcdWJhNzQsIFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NWMgXHVjMTIwXHVjNzc0IFx1YzEyMFx1YmQ4NFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2U2MFx1ZDMxMFx1YzVkMCBcdWFkZjhcdWI5YjAgXHVhZGY4XHViOWFjXHViNGRjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM5YzFcdWMxMjBcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0IFx1YzEzOCBcdWFlMDBcdWM3OTAoXHVkMmI4XHViOWFjXHVkNTBjXHViODFiKVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWRmOFx1YjlhY1x1YjRkY1x1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgTiAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWRmOFx1YjlhY1x1YjRkY1x1YzVkMCBcdWNjNDRcdWM2Y2NcdWM4MzggXHVjNzg4XHViMjk0IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWNjNDRcdWM2YjBcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmU0OCBcdWNlNzhcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICYjMzk7LiYjMzk7XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDJiOFx1YjlhY1x1ZDUwY1x1YjgxYlx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwNDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUUk9KS0UiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGFuZCBTbGF2a28gYXJlIHBsYXlpbmcgYSBuZXcgZ2FtZSwgJnF1b3Q7VHJvamtlJnF1b3Q7IChUcmlwbGV0cykuIEZpcnN0IHRoZXkgdXNlIGEgY2hhbGsgdG8gZHJhdyBhbiBOLWJ5LU4gc3F1YXJlIGdyaWQgb24gdGhlIHJvYWQuIFRoZW4gdGhleSB3cml0ZSBsZXR0ZXJzIGludG8gc29tZSBvZiB0aGUgc3F1YXJlcy4gTm8gbGV0dGVyIGlzIHdyaXR0ZW4gbW9yZSB0aGFuIG9uY2UgaW4gdGhlIGdyaWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBnYW1lIGNvbnNpc3RzIG9mIHRyeWluZyB0byBmaW5kIHRocmVlIGxldHRlcnMgb24gYSBsaW5lIGFzIGZhc3QgYXMgcG9zc2libGUuIFRocmVlIGxldHRlcnMgYXJlIGNvbnNpZGVyZWQgdG8gYmUgb24gdGhlIHNhbWUgbGluZSBpZiB0aGVyZSBpcyBhIGxpbmUgZ29pbmcgdGhyb3VnaCB0aGUgY2VudHJlIG9mIGVhY2ggb2YgdGhlIHRocmVlIHNxdWFyZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFmdGVyIGEgd2hpbGUgaXQgZ2V0cyBoYXJkZXIgdG8gZmluZCBuZXcgdHJpcGxldHMuIE1pcmtvIGFuZCBTbGF2a28gbmVlZCBhIHByb2dyYW0gdGhhdCBjb3VudHMgYWxsIHRoZSB0cmlwbGV0cywgc28gdGhhdCB0aGV5IGtub3cgaWYgdGhlIGdhbWUgaXMgb3ZlciBvciB0aGV5IG5lZWQgdG8gc2VhcmNoIGZ1cnRoZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDMgJmxlOyBOICZsZTsgMTAwKSwgdGhlIGRpbWVuc2lvbiBvZiB0aGUgZ3JpZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgTiBmb2xsb3dpbmcgbGluZXMgY29udGFpbnMgTiBjaGFyYWN0ZXJzIGRlc2NyaWJpbmcgdGhlIGdyaWQgJm5kYXNoOyB1cHBlcmNhc2UgbGV0dGVycyBhbmQgdGhlIGNoYXJhY3RlciAmIzM5Oy4mIzM5Oywgd2hpY2ggbWFya3MgYW4gZW1wdHkgc3F1YXJlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbnVtYmVyIG9mIHRyaXBsZXRzIG9uIGEgc2luZ2xlIGxpbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #3 3번