시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB130096990451751.488%

문제

총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

  1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
  2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
  3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
  4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력

'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

출력

첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

예제 입력 1

YYYYY
SYSYS
YYYYY
YSYYS
YYYYY

예제 출력 1

2

힌트

가능한 방법은 아래와 같다.

.....    .....
SYSYS    SYSYS
....Y    .Y...
....S    .S...
.....    .....
W3sicHJvYmxlbV9pZCI6IjE5NDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWJiMzhcdWIwOWMgXHVjZTYwXHVhY2Y1XHVjOGZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkMWQgMjVcdWJhODVcdWM3NTggXHVjNWVjXHVkNTU5XHVjMGRkXHViNGU0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWM1ZWNcdWQ1NTlcdWMwZGRcdWJjMThcdWM3NDAgNSZ0aW1lczs1XHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjYTlcdWM3OTAgXHVkNjE1XHVkMGRjXHViODVjIFx1Yzc5MFx1YjlhY1x1YWMwMCBcdWJjMzBcdWNlNThcdWI0MThcdWM1YzhcdWFjZTAsIFx1YzViY1x1YjljOCBcdWM5YzBcdWIwOThcdWM5YzAgXHVjNTRhXHVjNTQ0IFx1Yzc3NFx1YjJlNFx1YzE5Y1x1YWNmYyBcdWM3ODRcdWIzYzRcdWM1ZjBcdWM3NzRcdWI3N2NcdWIyOTQgXHViNDUwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWI0NTBcdWFjMDFcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwIFx1YjJlNFx1Yjk3OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHVkNzE4XHVjNWI0XHVjN2ExXHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNC4gXHVhY2U3IFx1YmFhOFx1YjRlMCBcdWM1ZWNcdWQ1NTlcdWMwZGRcdWM3NzQgJmxzcXVvO1x1Yzc3NFx1YjJlNFx1YzE5Y1x1ZDMwYyZyc3F1bztcdWM2NDAgJmxzcXVvO1x1Yzc4NFx1YjNjNFx1YzVmMFx1ZDMwYyZyc3F1bztcdWM3NTggXHViNDUwIFx1ZDMwY1x1Yjg1YyBcdWFjMDhcdWI3N2NcdWM5YzBcdWFjOGMgXHViNDE4XHVjNWM4XHVjNzNjXHViYTcwLCBcdWM1YmNcdWI5YzggXHVjOWMwXHViMDk4XHVjOWMwIFx1YzU0YVx1YzU0NCAmbHNxdW87XHVjNzg0XHViM2M0XHVjNWYwXHVkMzBjJnJzcXVvO1x1YWMwMCBcdWMxMzhcdWI4MjVcdWM3NDQgXHVkNjU1XHVjN2E1XHVjMmRjXHVkMGE0XHViYTcwICZsc3F1bztcdWM3NzRcdWIyZTRcdWMxOWNcdWQzMGMmcnNxdW87XHViOTdjIFx1YzcwNFx1ZDYxMVx1ZDU1OFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1YWUzMFx1Yzc1OFx1YzJkZFx1Yzc0NCBcdWIyOTBcdWIwODAgJmxzcXVvO1x1Yzc3NFx1YjJlNFx1YzE5Y1x1ZDMwYyZyc3F1bztcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YWNmY1x1YWMxMFx1ZDc4OCBcdWQ2MDRcdWM3YWNcdWM3NTggXHVjY2I0XHVjODFjXHViOTdjIFx1ZDNlY1x1YWUzMFx1ZDU1OFx1YWNlMCwgJmxzcXVvO1x1YzE4Y1x1YmIzOFx1YjA5YyBcdWNlNjBcdWFjZjVcdWM4ZmMmcnNxdW87XHViOTdjIFx1YWNiMFx1YzEzMVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YzBkZFx1Yzg3NCBcdWMyMThcdWIyZThcdWM3ODRcdWM3NDQgXHVhZTY4XHViMmVjXHVjNTU4XHViMmU0LiAmbHNxdW87XHVjMThjXHViYjM4XHViMDljIFx1Y2U2MFx1YWNmNVx1YzhmYyZyc3F1bztcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFkZGNcdWNlNTlcdWM3NDQgXHViOWNjXHVjODcxXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWM3NzRcdWI5ODRcdWM3NzQgXHVjNzc0XHViOTg0XHVjNzc4IFx1YjljY1x1ZDA3YywgN1x1YmE4NVx1Yzc1OCBcdWM1ZWNcdWQ1NTlcdWMwZGRcdWI0ZTRcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhYzE1XHVkNTVjIFx1YWNiMFx1YzE4ZFx1YjgyNVx1Yzc0NCBcdWM3MDRcdWQ1NzQsIDdcdWJhODVcdWM3NTggXHVjNzkwXHViOWFjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWFjMDBcdWI4NWNcdWIwOTggXHVjMTM4XHViODVjXHViODVjIFx1YmMxOFx1YjRkY1x1YzJkYyBcdWM3NzhcdWM4MTFcdWQ1NzQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVkNjU0XHVkNTY5XHVhY2ZjIFx1YmM4OFx1YzYwMVx1Yzc0NCBcdWM3MDRcdWQ1NzQsIFx1YmMxOFx1YjRkY1x1YzJkYyAmbHNxdW87XHVjNzc0XHViMmU0XHVjMTljXHVkMzBjJnJzcXVvO1x1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWI4NWNcdWI5Y2MgXHVhZDZjXHVjMTMxXHViNDIwIFx1ZDU0NFx1YzY5NFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWRmOFx1YjdlY1x1YjA5OCBcdWMwZGRcdWM4NzRcdWM3NDQgXHVjNzA0XHVkNTc0LCAmbHNxdW87XHVjNzc0XHViMmU0XHVjMTljXHVkMzBjJnJzcXVvO1x1YWMwMCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVjNmIwXHVjNzA0XHViOTdjIFx1YzgxMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyA3XHViYTg1XHVjNzU4IFx1ZDU1OVx1YzBkZCBcdWM5MTEgJmxzcXVvO1x1Yzc3NFx1YjJlNFx1YzE5Y1x1ZDMwYyZyc3F1bztcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzc0IFx1YzgwMVx1YzViNFx1YjNjNCA0XHViYTg1IFx1Yzc3NFx1YzBjMVx1Yzc0MCBcdWJjMThcdWI0ZGNcdWMyZGMgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNWVjXHVkNTU5XHVjMGRkXHViYzE4XHVjNzU4IFx1Yzc5MFx1YjlhYyBcdWJjMzBcdWNlNThcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgJmxzcXVvO1x1YzE4Y1x1YmIzOFx1YjA5YyBcdWNlNjBcdWFjZjVcdWM4ZmMmcnNxdW87XHViOTdjIFx1YWNiMFx1YzEzMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+JiMzOTtTJiMzOTsoXHVjNzc0XHViMmU0JmxzcXVvO1x1YzE5YyZyc3F1bztcdWQzMGNcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBjNCkgXHViNjEwXHViMjk0ICYjMzk7WSYjMzk7KFx1Yzc4NFx1YjNjNCZsc3F1bztcdWM1ZjAmcnNxdW87XHVkMzBjXHVjNzU4IFx1ZDU1OVx1YzBkZFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYzQpXHVjNzQ0IFx1YWMxMlx1YzczY1x1Yjg1YyBcdWFjMTZcdWIyOTQgNSo1IFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWFjZjVcdWJjMzEgXHVjNWM2XHVjNzc0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgXHViMmU0XHVjMTJmIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgJmxzcXVvO1x1YzE4Y1x1YmIzOFx1YjA5YyBcdWNlNjBcdWFjZjVcdWM4ZmMmcnNxdW87XHViOTdjIFx1YWNiMFx1YzEzMVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4uLi4uLiAgICAuLi4uLlxyXG5TWVNZUyAgICBTWVNZU1xyXG4uLi4uWSAgICAuWS4uLlxyXG4uLi4uUyAgICAuUy4uLlxyXG4uLi4uLiAgICAuLi4uLlxyXG48XC9wcmU+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTk0MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJpZ2dpbmcgdGhlIEJvdmluZSBFbGVjdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+SXQmIzM5O3MgZWxlY3Rpb24gdGltZS4gVGhlIGZhcm0gaXMgcGFydGl0aW9uZWQgaW50byBhIDV4NSBncmlkIG9mIGNvdyBsb2NhdGlvbnMsIGVhY2ggb2Ygd2hpY2ggaG9sZHMgZWl0aGVyIGEgSG9sc3RlaW4gKCYjMzk7WSYjMzk7KSBvciBKZXJzZXkgKCYjMzk7UyYjMzk7KSBjb3cuIFRoZSBKZXJzZXlzIHdhbnQgdG8gY3JlYXRlIGEgdm90aW5nIGRpc3RyaWN0IG9mIDcgY29udGlndW91cyAodmVydGljYWxseSBvciBob3Jpem9udGFsbHkpIGNvdyBsb2NhdGlvbnMgc3VjaCB0aGF0IHRoZSBKZXJzZXlzIG91dG51bWJlciB0aGUgSG9sc3RlaW5zLiBIb3cgbWFueSB3YXlzIGNhbiB0aGlzIGJlIGRvbmUgZm9yIHRoZSBzdXBwbGllZCBncmlkPzxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lcyAxLi41OiBFYWNoIG9mIHRoZSBmaXZlIGxpbmVzIGNvbnRhaW5zIGZpdmUgY2hhcmFjdGVycyBwZXIgbGluZSwgZWFjaCAmIzM5O1kmIzM5OyBvciAmIzM5O1MmIzM5Oy4gTm8gc3BhY2VzIGFyZSBwcmVzZW50LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IFRoZSBudW1iZXIgb2YgZGlzdGluY3QgZGlzdHJpY3RzIG9mIDcgY29ubmVjdGVkIGNvd3Mgc3VjaCB0aGF0IHRoZSBKZXJzZXlzIG91dG51bWJlciB0aGUgSG9sc3RlaW5zIGluIHRoZSBkaXN0cmljdC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiI8cD5UaGUgdHdvIHBvc3NpYmxlIGRpc3RyaWN0cyBhcmU6PFwvcD5cclxuXHJcbjxwcmU+XHJcbi4uLi4uICAgICAgICAgICAgICAgIC4uLi4uXHJcblNZU1lTICAgICAgICAgICAgICAgIFNZU1lTXHJcbi4uLi5ZICAgICAgIGFuZCAgICAgIC5ZLi4uXHJcbi4uLi5TICAgICAgICAgICAgICAgIC5TLi4uXHJcbi4uLi4uICAgICAgICAgICAgICAgIC4uLi4uPFwvcHJlPlxyXG5cclxuPHA+QW55IG90aGVyIHBvc3NpYmxlIGRpc3RyaWN0IHdpdGggc2V2ZW4gY293cyBoYXMgZmV3ZXIgdGhhbiA0IEplcnNleXMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2004-2005 Season > USACO February 2005 Contest > Silver 2번

  • 문제의 오타를 찾은 사람: YunGoon