試験問題を解いてみた
人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。
3時間でここまで。全経路をたどってしまうので、Lv3扱いで不合格(^^;
与えられた迷路を、1歩ごとに盤面を新たに生成しながら再帰していく。最初に作るものとしては妥当かと。
しかし、経路をすべて探索してしまうので、1本道だけならそれほどでもないが、広いスペースが存在するととたんに探索数が多くなってしまう。ということでLv3扱い。
#include <stdio.h> #include <string.h> #include <assert.h> #define COLUMN 26 #define LINE 13 typedef struct { int x; int y; } point_t; typedef struct { char c[LINE][COLUMN+1]; } maze_t; point_t direction[4] = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } }; maze_t min_maze = { "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$", "$$$$$$$$$$$$$$$$$$$$$$$$$$" }; int can_move (maze_t *m, point_t p, int d) { char c = m->c[p.x + direction[d].x][p.y + direction[d].y]; return (c == ' ' || c == 'G'); } int is_goal (maze_t *m, point_t p) { int i; for (i=0; i<LINE; i++) if (m->c[p.x][p.y] == 'G') return 1; return 0; } point_t move_point (maze_t *m, point_t p, int d) { point_t ret; ret.x = p.x + direction[d].x; ret.y = p.y + direction[d].y; return ret; } void set_point (maze_t *m, point_t p, char c) { m->c[p.x][p.y] = c; } int count_path (maze_t *m) { int i, j, s = 0; for (i=0; i<LINE; i++) for (j=0; j<COLUMN; j++) if (m->c[i][j] == '$') s++; return s; } void go_maze (maze_t m, point_t p) { int d, c = count_path (&m); if (is_goal (&m, p)) { if (c < count_path (&min_maze)) min_maze = m; return; } set_point (&m, p, '$'); for (d=0; d<4; d++) { if (can_move (&m, p, d)) { point_t pp = move_point (&m, p, d); go_maze (m, pp); } } } void print_maze (maze_t *m) { int i; for (i=0; i<LINE; i++) printf ("%s\n", m->c[i]); } int main (void) { maze_t question = { "**************************", "*S* * *", "* * * * ************* *", "* * * ************ *", "* * *", "************** ***********", "* *", "** ***********************", "* * G *", "* * *********** * *", "* * ******* * *", "* * *", "**************************" }; maze_t answer = { "**************************", "*S* * $$$ *", "*$* *$$*$ ************* *", "*$* $$* $$$************ *", "*$$$$* $$$$$ *", "**************$***********", "* $$$$$$$$$$$$$ *", "**$***********************", "* $$$$$*$$$$$$$$$$$$$$G *", "* * $$$ *********** * *", "* * ******* * *", "* * *", "**************************" }; point_t start={1,1}; go_maze (question, start); set_point (&min_maze, start, 'S'); printf ("------------------------------\n"); print_maze (&min_maze); { int i; for (i=0; i<LINE; i++) { assert (count_path(&min_maze) == count_path(&answer)); } } return 0; }
さらに30分かけて、無駄な探索をしないように修正。各マスにスタートからの距離を記録しておくことによって実現。これで一応Lv4だけど、1歩ごとに盤面を保存しながら再帰しているので、少し大きくなると動かなくなってしまう。
diff --git a/meiro.c b/meiro.c index 22cb7d7..c6cfc68 100644 --- a/meiro.c +++ b/meiro.c @@ -21,6 +21,35 @@ point_t direction[4] = { +int maze_count[LINE][COLUMN] = { + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, + { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, + 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff } +}; + @@ -92,6 +121,12 @@ go_maze (maze_t m, point_t p) void go_maze (maze_t m, point_t p) { int d, c = count_path (&m); if (is_goal (&m, p)) { if (c < count_path (&min_maze)) min_maze = m; return; } + if (c >= maze_count[p.x][p.y]) + { + return; + } + + maze_count[p.x][p.y] = c; set_point (&m, p, '$'); for (d=0; d<4; d++) { if (can_move (&m, p, d)) { point_t pp = move_point (&m, p, d); go_maze (m, pp); } } }
さらに1歩ずつ盤面をコピーしていたのをやめた。各マスのスタートからの距離だけで、次の1歩を求めて進んでいく。再帰のコストが低い言語なら大きな盤面でも大丈夫なはず。
#include <stdio.h> #include <string.h> #include <assert.h> #define COLUMN 26 #define LINE 13 typedef struct { int x; int y; } point_t; typedef struct { char c[LINE][COLUMN+1]; } maze_t; point_t direction[4] = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } }; maze_t question = { "**************************", "*S* * *", "* * * * ************* *", "* * * ************ *", "* * *", "************** ***********", "* *", "** ***********************", "* * G *", "* * *********** * *", "* * ******* * *", "* * *", "**************************" }; maze_t answer = { "**************************", "*S* * $$$ *", "*$* *$$*$ ************* *", "*$* $$* $$$************ *", "*$$$$* $$$$$ *", "**************$***********", "* $$$$$$$$$$$$$ *", "**$***********************", "* $$$$$*$$$$$$$$$$$$$$G *", "* * $$$ *********** * *", "* * ******* * *", "* * *", "**************************" }; int maze_count[LINE][COLUMN] = { { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff }, { 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff } }; int can_move (point_t p, int d) { char c = question.c[p.x + direction[d].x][p.y + direction[d].y]; return (c == ' ' || c == 'G'); } int is_point (point_t p, char c) { int i; for (i=0; i<LINE; i++) if (question.c[p.x][p.y] == c) return 1; return 0; } point_t move_point (point_t p, int d) { point_t ret; ret.x = p.x + direction[d].x; ret.y = p.y + direction[d].y; return ret; } void set_point (point_t p, char c) { question.c[p.x][p.y] = c; } int count_path (maze_t *m) { int i, j, s = 0; for (i=0; i<LINE; i++) for (j=0; j<COLUMN; j++) if (m->c[i][j] == '$') s++; return s; } void print_count (void) { int i, j; for (i=0; i<LINE; i++) { for (j=0; j<COLUMN; j++) printf ("%04x ", maze_count[i][j]); printf ("\n"); } } void go_maze (point_t p) { int d; if (is_point (p, 'G')) return; for (d=0; d<4; d++) { if (can_move (p, d)) { point_t pp = move_point (p, d); if (maze_count[pp.x][pp.y] > maze_count[p.x][p.y] + 1) { maze_count[pp.x][pp.y] = maze_count[p.x][p.y] + 1; go_maze (pp); } } } } void print_maze (maze_t *m) { int i; for (i=0; i<LINE; i++) printf ("%s\n", m->c[i]); } int main (void) { point_t p, pp, start={1,1}, goal={8,22}; int i, d, count; maze_count[start.x][start.y] = 0; go_maze (start); p = goal; count = maze_count[goal.x][goal.y]; do { set_point (p, '$'); count--; for (d=0; d<4; d++) { pp = move_point (p, d); if (count == maze_count[pp.x][pp.y]) break; } p = pp; } while (d != 4 && ! is_point (p, 'S')); set_point (goal, 'G'); print_maze (&question); for (i=0; i<LINE; i++) { assert (count_path(&answer) == count_path(&answer)); } return 0; }
久しぶりに仕事以外でコード書いたな。
