시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB303654540.541%

문제

5 x 5 행렬에 대문자 알파벳이 하나씩 들어간 퍼즐이 있다. 그리고 이 행렬에서 주어진 단어들을 찾는 것이다. 찾는 방법은 임의의 시작점에서 시작하여 인접한 8방향으로 뻗어나가면서 알파벳을 이어나가는 것이다. 이때 같은 칸을 두 번 이상 방문할 수 없다. 찾을 단어들은 문제와 함께 배포된 dict.txt에 들어있는 단어들이다.

Z C C D X
K Q M N B
U O W Z Y
F C O I J
P A Q Z T

위와 같은 퍼즐이 있을 때 CAP, COW, COOK 등은 퍼즐에서 찾을 수 있지만 COD, PACK 등은 찾을 수 없다.

문제는 퍼즐이 주어졌을 때, 퍼즐 속에 총 몇 개의 단어가 있는지 구하는 것이다.

입력

다섯 줄에 걸쳐 5 x 5알파벳 퍼즐이 공백으로 구분되어 주어진다.

출력

첫 줄에 포함되는 총 단어 개수를 출력한다.

예제 입력 1

Z C C D X
K Q M N B
U O W Z Y
F C O I J
P A Q Z T

예제 출력 1

8

힌트

dict.txt는 여기에 압축되어 있다.

W3sicHJvYmxlbV9pZCI6IjExNjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWM1YjRcdWQzN2NcdWM5OTAiLCJkZXNjcmlwdGlvbiI6IjxwPjUgeCA1IFx1ZDU4OVx1YjgyY1x1YzVkMCBcdWIzMDBcdWJiMzhcdWM3OTAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzc0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWI0ZTRcdWM1YjRcdWFjMDQgXHVkMzdjXHVjOTkwXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzc3NCBcdWQ1ODlcdWI4MmNcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWNjM2VcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVjNWVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyA4XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YmVkN1x1YzViNFx1YjA5OFx1YWMwMFx1YmE3NFx1YzExYyBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDQgXHVjNzc0XHVjNWI0XHViMDk4XHVhYzAwXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNzc0XHViNTRjIFx1YWMxOVx1Yzc0MCBcdWNlNzhcdWM3NDQgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1Y2MzZVx1Yzc0NCBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDAgXHViYjM4XHVjODFjXHVjNjQwIFx1ZDU2OFx1YWVkOCBcdWJjMzBcdWQzZWNcdWI0MWMgZGljdC50eHRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YjJlOFx1YzViNFx1YjRlNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuWiBDIEMgRCBYXHJcbksgUSBNIE4gQlxyXG5VIE8gVyBaIFlcclxuRiBDIE8gSSBKXHJcblAgQSBRIFogVDxcL3ByZT5cclxuXHJcbjxwPlx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkMzdjXHVjOTkwXHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMgQ0FQLCBDT1csIENPT0sgXHViNGYxXHVjNzQwIFx1ZDM3Y1x1Yzk5MFx1YzVkMFx1YzExYyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YzljMFx1YjljYyBDT0QsIFBBQ0sgXHViNGYxXHVjNzQwIFx1Y2MzZVx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVkMzdjXHVjOTkwXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDM3Y1x1Yzk5MCBcdWMxOGRcdWM1ZDAgXHVjZDFkIFx1YmE4NyBcdWFjMWNcdWM3NTggXHViMmU4XHVjNWI0XHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHViMmU0XHVjMTJmIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgNSB4IDVcdWM1NGNcdWQzMGNcdWJjYjMgXHVkMzdjXHVjOTkwXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1Y2QxZCBcdWIyZThcdWM1YjQgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+ZGljdC50eHRcdWIyOTQgPGEgaHJlZj1cImh0dHBzOlwvXC9kMmdkNnBjMDM0d2N0YS5jbG91ZGZyb250Lm5ldFwvZGF0YVwvMTE2NS56aXBcIj5cdWM1ZWNcdWFlMzA8XC9hPlx1YzVkMCBcdWM1NTVcdWNkOTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTE2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvZ2dsZSIsImRlc2NyaXB0aW9uIjoiPHA+TGlrZSBldmVyeW9uZSBlbHNlIG9uIHRoZWlyIHZhY2F0aW9uLCB0aGUgY293cyBwbGF5IHRoZSBjb3cgdmVyc2lvbiBvZiB0aGUgd29yZCBnYW1lIGNhbGxlZCBCb2dnbGU6IENvZ2dsZS4gSXQmIzM5O3MgYSBzaW1pbGFyIGdhbWUgd2hlcmUgMjUgbGV0dGVyIGRpY2UgYXJlIHJvbGxlZCBpbnRvIGEgbWF0cml4IGxpa2UgdGhpcyBvbmU6PFwvcD5cclxuXHJcbjxwcmU+XHJcbiAgICAgICAgICAgWiBDIEMgRCBYXHJcbiAgICAgICAgICAgSyBRIE0gTiBCXHJcbiAgICAgICAgICAgVSBPIFcgWiBZXHJcbiAgICAgICAgICAgRiBDIE8gSSBKXHJcbiAgICAgICAgICAgUCBBIFEgWiBUXHJcbjxcL3ByZT5cclxuXHJcbjxwPldvcmRzIGFyZSBtYWRlIChhbmQgdGh1cyBwb2ludHMgc2NvcmVkKSBieSBzdGFydGluZyBhdCBzb21lIGxldHRlciBhbmQgcHJvY2VlZGluZyB0byBvbmUgb2YgaXRzIChhcyBtYW55IGFzKSBlaWdodCBuZWlnaGJvcnMsIGV0Yy4gdW50aWwgdGhlIHN1Y2Nlc3NpdmUgbGV0dGVycyBzcGVsbCBvdXQgYSB3b3JkIGZyb20gYSBkaWN0aW9uYXJ5PFwvcD5cclxuXHJcbjxwPkluIHRoZSBtYXRyaXggYWJvdmUsIHRoZSBsb3dlciAmIzM5O0MmIzM5OyBjYW4gYmUgdXNlZCB0byBmb3JtIHRoZSB3b3JkcyAmcXVvdDtDQVAmcXVvdDssICZxdW90O0NPVyZxdW90OywgYW5kICZxdW90O0NPT0smcXVvdDsgKGJ1dCBub3QgJnF1b3Q7Q09EJnF1b3Q7IG9yICZxdW90O1BBQ0smcXVvdDspLiBUaGUgY29tcGxldGUgbGlzdCBvZiBkaWN0aW9uYXJ5IHdvcmRzIGZvciB0aGUgYWJvdmUgc3F1YXJlIGlzOiAmcXVvdDtDQVAmcXVvdDssICZxdW90O0NPT0smcXVvdDssICZxdW90O0NPVyZxdW90OywgJnF1b3Q7T1dOJnF1b3Q7LCAmcXVvdDtXSVQmcXVvdDssICZxdW90O1dPTyZxdW90OywgJnF1b3Q7Wk9PJnF1b3Q7LCBhbmQgJnF1b3Q7Wk9PTSZxdW90Oy48XC9wPlxyXG5cclxuPHA+WW91ciBwcm9ncmFtIHNob3VsZCByZWFkIHRoZSBkaWN0aW9uYXJ5IGZyb20gZmlsZSBkaWN0LnR4dCAod2hpY2ggaXMgYWxwaGFiZXRpemVkIGFuZCBoYXMgZmV3ZXIgdGhhbiAyNSwwMDAgd29yZHM7IGVhY2ggd29yZCBpcyBubyBsb25nZXIgdGhhbiAyMCBjaGFyYWN0ZXJzKS4gVGhlIGFjdHVhbCBkaWN0aW9uYXJ5IGNvbnRlbnRzIGNhbiBiZSBpbnNwZWN0ZWQgYXQgPGEgaHJlZj1cImh0dHBzOlwvXC9kMmdkNnBjMDM0d2N0YS5jbG91ZGZyb250Lm5ldFwvZGF0YVwvMTE2NS56aXBcIj5oZXJlPFwvYT4uPFwvcD5cclxuXHJcbjxwPkhlbHAgQmVzc2llIHNlZSBob3cgZ29vZCBzaGUgY2FuIGRvLiBSZWFkIGluIGZpdmUgcm93cyBvZiBmaXZlIGxldHRlcnMgdGhhdCByZXByZXNlbnQgdGhlIGRpY2UgYW5kIHNlZSBob3cgbWFueSB3b3JkcyBmcm9tIHRoZSBkaWN0aW9uYXJ5IGNhbiBiZSBmb3JtZWQuICZuYnNwO0RvbiYjMzk7dCB1c2UgYW55IGdpdmVuIGRpZSYjMzk7cyBsZXR0ZXIgdHdpY2UgaW4gdGhlIHNhbWUgd29yZC48XC9wPlxyXG5cclxuPHA+Q291bnQgdGhlIG51bWJlciBvZiB3b3JkcyB0aGF0IGNhbiBiZSBmb3JtZWQgKGEgbnVtYmVyIHRoYXQgbWlnaHQgd2VsbCBiZSBzbWFsbGVyIHRoYW4gdGhlIG51bWJlciBvZiB3YXlzIGEgd29yZCBhIGNhbiBiZSBmb3JtZWQgc2luY2Ugd29yZHMgbWlnaHQgYmUgZm9ybWVkIGluIG1vcmUgdGhhbiBvbmUgd2F5KS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZXMgMS4uNTogTGluZSBpIGNvbnRhaW5zIGZpdmUgc3BhY2Utc2VwYXJhdGVkIHVwcGVyLWNhc2UgbGV0dGVycyB0aGF0IGFyZSByb3cgaTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgbnVtYmVyIG9mIHdvcmRzIGluIHRoZSBkaWN0aW9uYXJ5IHRoYXQgY2FuIGJlIGZvcm1lZCB1c2luZyB0aGUgZGVzY3JpYmVkIHJ1bGVzPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO February 2009 Contest > Bronze 3번 (수정)

  • 문제를 번역한 사람: author6
  • 문제의 오타를 찾은 사람: isku

채점 및 기타 정보

  • 소스 코드의 크기는 65536B을 넘을 수 없다.