こんなのを見つけました → 第６回日本情報オリンピック 予選
腕に覚えのある高校生以下のワカゾーたちがGeekっぷりを競い合うですね。
京都の街を歩いて学校に行くですよ。
途中あちこちの工事中を避けて何通りの経路があるか、と。
おもしろそぉなので解いてみよぉ。
どこも工事中でないなら、(1,1)→(5,4) なんだから
とにかく東に4(=5-1)区画, 北に3(=4-1)区画進めばいい。
つまり EEEENNN を並びかえてできるルートの組み合わせがすべて。
その中から工事中の点を通過するものを除けばよかろ。
#include <iostream> // cout, endl
#include <utility> // pair
#include <algorithm> // next_permutation
#include <set> // set
#include <string> // string
using namespace std;
int main() {
typedef std::pair<int,int> point; // 点
set<point> holes; // 工事中の集合
point start(1,1); // 太郎くんち
point goal(5,4); // JOI高校
holes.insert(point(2,2)); // あちら
holes.insert(point(2,3)); // こちらで
holes.insert(point(4,2)); // 工事中
// 東に進める分の'E'と北に進める分の'N'を繋いだ文字列を作る
string direction = string(goal.first-start.first,'E') +
string(goal.second-start.second,'N');
do {
point p = start; // 太郎くんちを起点とし、
for ( string::iterator iter = direction.begin(); iter != direction.end(); ++iter ) {
// 'N'なら北へ/'E'なら東に進み、
if ( *iter == 'N' ) ++p.second; else ++p.first;
// そこが工事中なら諦める
if ( holes.find(p) != holes.end() ) { break; }
}
// JOI高校にたどり着いた?
if ( p == goal ) {
cout << direction << endl;
}
// 次の組み合わせで歩く (next_permutation でズボラこいただ♪)
} while ( next_permutation(direction.begin(), direction.end()) );
}
実行結果:
EEEENNN
EENNEEN
EENNENE
EENNNEE
NNNEEEE
おー、あってるあってる♪
# VB, C#, Java 等々、腕試しにやってみそー