-
Notifications
You must be signed in to change notification settings - Fork 0
/
gpcc10.htm
90 lines (69 loc) · 6.93 KB
/
gpcc10.htm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
<HTML>
<HEAD>
<TITLE>GPCC2010問題</TITLE>
</HEAD>
<BODY>
<H1>GPCC2010問題</H1>
<HR>
<H2><A NAME="g1">ハイパーロボット(Ricochet Robots)</A></H2>
<P>何人でも行えるパズルゲームである。16×16のボードにロボットが4台置いてある。ボード上の指定されたゴールに、なるべく少ない手数で、指定されたロボットを移動させることを目指す。
<P>各ロボットの動きには制限がある。障害物に当たるまでは止まらずに、縦または横に直進する。障害物は、ボードの端、ボードにあらかじめ描かれた壁、他のロボットである。各ロボットの直進1回を1手と数える。
<P>人間同士でプレイする場合には、ロボットを動かす前に手順を考えて、手数を宣言する。詳しくは、合同会社ニューゲームズオーダーの<A HREF="http://www.newgamesorder.com/games/ricochetrobots">Ricochet Robots</A>にある日本語のルールを参照。
<P>以下の盤面は、今年のプログラミング・シンポジウムの夜の自由討論の時間に、参加者同士で勝負したときの一場面である。太い線は壁、<FONT COLOR=BLUE>☆</FONT>は今回のゴール、<FONT COLOR=BLUE>★</FONT>はゴールに動かすべきロボット、<FONT COLOR=YELLOW>●</FONT><FONT COLOR=GREEN>▲</FONT><FONT COLOR=RED>■</FONT>は障害物として使えるロボットである。
<PRE STYLE="color: black; background-color: white; line-height: 100%;">
┏━┯━┯━┯━┯━┳━┯━┯━┯━┯━┯━┳━┯━┯━┯━┯━┓
┃□│□│□│□│□┃□│□│□│□│□│□┃□│□│□│□│<FONT COLOR=YELLOW>●</FONT>┃
┠─┼─┏━┥─┼─┸─┼─┼─┼─┼─┼─┸─┏━┥─┼─┼─┨
┃□│□┃□│□│□│□│□│□│□│□│□│□┃<FONT COLOR=GREEN>▲</FONT>│□│□│□┃
┠─┼─┸─┼─┼─┼─┼─┼─┼─┼─┼─┼─┸─┼─┰─┼─┨
┃□│□│□│□│□│□│□│□│□│□│□│□│□│□┃<FONT COLOR=RED>■</FONT>│□┃
┠─┼─┼─┼─┼─┼─┰─┼─┰─┼─┼─┼─┼─┼─┗━┥─┨
┃□│□│□│□│□│□┃□│□┃□│□│□│□│□│□│□│□┃
┠─┼─┼─┼─┼─┼─┗━┥─┗━┥─┼─┼─┼─┼─┼─┼─┨
┃□│□│□│□│□│□│□│□│□│□│□│□│□│□│□│□┃
┣━┥─┼─┼─┝━┓─┼─┼─┼─┼─┰─┼─┼─┼─┼─┝━┫
┃□│□│□│□│□┃□│□│□│□│□┃□│□│□│□│□│□┃
┠─┼─┰─┼─┼─┸─┼─┼─┼─┝━┛─┝━┓─┼─┼─┼─┨
┃□│□┃□│□│□│□│□│□│□│□│□│□┃□│□│□│□┃
┠─┝━┛─┼─┼─┼─┼─┏━━━┓─┼─┼─┸─┼─┼─┼─┨
┃□│□│□│□│□│□│□┃□│□┃□│□│□│□│□│□│□┃
┠─┼─┼─┼─┼─┰─┼─┃─┼─┃─┼─┼─┼─┼─┼─┼─┨
┃□│□│□│□│□┃□│□┃□│□┃□│□│□│□│□│□│□┃
┠─┼─┏━┥─┼─┗━┥─┗━━━┛─┼─┼─┝━┓─┼─┼─┨
┃□│□┃□│□│□│□│□│□│□│□│□│□│□┃□│□│□┃
┠─┼─┸─┼─┼─┼─┼─┼─┼─┰─┼─┼─┼─┸─┼─┝━┫
┃□│□│□│□│□│□│□│□│□┃□│□│□│□│□│□│□┃
┠─┼─┼─┼─┼─┼─┼─┼─┼─┗━┥─┼─┼─┼─┼─┼─┨
┃□│□│□│□│□│□│□│□│□│□│□│□│□│□│□│□┃
┣━┥─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┨
┃□│□│□│□│□│□│□│□│□│□│□│□│□│□│□│□┃
┠─┼─┼─┼─┝━┓─┼─┼─┼─┼─┼─┼─┼─┼─┼─┰─┨
┃□│□│□│□│<FONT COLOR=BLUE>☆</FONT>┃□│□│□│□│□│□│□│□│□│□┃□┃
┠─┼─┰─┼─┼─┸─┼─┼─┼─┏━┥─┼─┼─┼─┝━┛─┨
┃□│□┃□│□│□│□│□│□│□┃□│□│□│□│□│□│□┃
┠─┝━┛─┼─┼─┼─┰─┼─┼─┸─┼─┰─┼─┼─┼─┼─┨
┃□│□│□│□│□│□┃□│□│□│□│<FONT COLOR=BLUE>★</FONT>┃□│□│□│□│□┃
┗━┷━┷━┷━┷━┷━┻━┷━┷━┷━┷━┻━┷━┷━┷━┷━┛
</PRE>
<P>人間同士では、真の最小手数を求める必要はない。この勝負では、28手、25手、20手の宣言があり、20手を宣言した人が勝った。その手順はおそらく以下のようなものであった(例えば<FONT COLOR=GREEN>▲</FONT>を右、下、左の順に止まるまで動かすことを、<FONT COLOR=GREEN>▲</FONT>→↓←と書く)。
<PRE>
<FONT COLOR=GREEN>▲</FONT>→↓←
<FONT COLOR=RED>■</FONT>→↓←(<FONT COLOR=GREEN>▲</FONT>で止まる)
<FONT COLOR=YELLOW>●</FONT>↓←(<FONT COLOR=RED>■</FONT>で止まる)
<FONT COLOR=GREEN>▲</FONT>↑→↓←(<FONT COLOR=YELLOW>●</FONT>で止まる)
<FONT COLOR=GREEN>▲</FONT>↓→
<FONT COLOR=BLUE>★</FONT>←↑←(<FONT COLOR=YELLOW>●</FONT>で止まる)
<FONT COLOR=BLUE>★</FONT>↓→(<FONT COLOR=GREEN>▲</FONT>で止まる)
<FONT COLOR=BLUE>★</FONT>↑
</PRE>
<P>計算機では、最小手数は簡単に求まってしまうはずである。真の最小手数はいくつであろうか。[2010-6-16解答あり]
<P>これだけでは簡単なので、次は、ロボットの初期位置を任意に選べるとする。上の盤面で、ロボットの初期位置だけを変えて、最小手数が最も大きくなるような配置はどのようなものだろうか。[2010-6-16解答あり]
<P><A HREF="10g1.htm">解答へ</A>
<HR>
<H2><A NAME="g2">コリドール(Quoridor)</A></H2>
<P>2人で行うボードゲームである(4人で行うルールもある)。9×9のボードの自分側の辺の中央に自分の駒を置いて始め、先に対岸に着いたほうが勝ちである。2人で交互に、駒を1マス進めるか、長さ2の壁をマスの境界に置く。ただし、対岸に着けないように壁を置いてはいけない。
<P><A HREF="http://www.vector.co.jp/soft/winnt/game/se476678.html">ARiAdoNE</A>というフリーソフトがある(ルール説明も含まれている)ので、まずはこれに勝てるようなプログラムを作ってみよう。
<HR>
<P style="height:1000px">以下余白</P>
</BODY>
</HTML>