ImagineCup 2008、問題サンプルのプログラム

このエントリーをはてなブックマークに追加
投稿者:chikunai 投稿日時:2010-12-26(日) 21:56

昔の作品公開です。

2008年、ImagineCup 2008で高橋さんが3位に入賞しました。それを伝える日本経済新聞の記事に、問題サンプルが出ていました。この問題サンプルに取り組んだプログラムを公開します。

記事のリンクは切れています。
http://it.nikkei.co.jp/business/news/index.aspx?n=MMIT00000028072008&cp=1

問題はこちら

Quote:

青(湿地)と緑(陸地)にバラバラに塗られた120×120のマス目があり、
隣り合った青と緑を入れ替えていくことで
もっとも最小限で青をすべてつなげるにはどうすればよいか

作った作品はこちら。見やすくしてあります。

http://www.chikunai.net/goods/kadai2.php

所感・考察

当時、2~3時間程度で作りました。一応、最小の手順で青がつながります。
120×120のマス目や、それ以上のマス目のときは、このアルゴリズムではつらいと思います。
上下左右どの方向に動かすかの評価方法に改良の余地あり。たとえば、一歩先の手の評価だけでなく、方向全体をサンプリングして、どれくらい青がいるかを評価に加えられると、より良さそうです。

ちょっとした頭の体操にどうぞ。

添付サイズ
kadai2.php_.txt6.84 KB



コメント(0)

新しいコメントの投稿

このフィールドの内容は非公開にされ、公表されることはありません。
  • 使用できるHTMLタグ: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <img> <table> <tr> <th> <td>
  • 行と段落は自動的に折り返されます。
  • You can use BBCode tags in the text. URLs will automatically be converted to links.
  • 次のタグを使用してソースコード構文をハイライトすることができます。: <code>, <blockcode> The supported tag styles are: <foo>, [foo].
  • You may insert videos with [video:URL]
  • ウェブページアドレスとメールアドレスは、自動的にハイパーリンクに変換されます。

書式オプションに関するより詳しい情報...

CAPTCHA
この問題はユーザが人間であるかどうかをテストし、スパムによる自動投稿を防ぐためのものです。
Image CAPTCHA
Enter the characters shown in the image.
Drupal theme by Kiwi Themes.