迷路の最短経路

人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。

ダイクストラとか大昔に書いた記憶があるけど完全に忘却の彼方だったので，適当にCで書いたらこうなった。スタート地点から深さ優先で探索してコストを求めていく感じで。普通はキューで探索する頂点を管理するところだけど実装が面倒だったので再帰でごまかした。

maze.c

#include <stdio.h>

#define W 26
#define H 13

int cost[H][W];
char maze[H][W] = {
	"**************************",
	"*S* *                    *",
	"* * *  *  *************  *",
	"* *   *    ************  *",
	"*    *                   *",
	"************** ***********",
	"*                        *",
	"** ***********************",
	"*      *              G  *",
	"*  *      *********** *  *",
	"*    *        ******* *  *",
	"*       *                *",
	"**************************",
};
int diff[4][2] = {
	{ 0, -1 },
	{ -1, 0 },
	{ 1, 0 },
	{ 0, 1 },
};

void solve(int x, int y)
{
	int i, j, k;
	int current;
	
	current = cost[y][x];
	
	if (current < 0) {
		return;
	}
	
	for (k=0;k<4;k++) {
		i = y + diff[k][1];
		j = x + diff[k][0];
		//bounds
		if (i < 0 || j < 0 || i >= H || j >= W) {
			continue;
		}
		//wall
		if (maze[i][j] == '*') {
			continue;
		}
		//update
		if (cost[i][j] < 0 || current + 1 < cost[i][j]) {
			cost[i][j] = current + 1;
			solve(j, i);
		}
	}
}

void output_maze()
{
	int i, j;
	
	for (i=0;i<H;i++) {
		for (j=0;j<W;j++) {
			printf("%c", maze[i][j]);
		}
		printf("\n");
	}
}

void output_cost()
{
	int i, j;
	
	for (i=0;i<H;i++) {
		for (j=0;j<W;j++) {
			printf("%3d ", cost[i][j]);
		}
		printf("\n");
	}
}

int main(void)
{
	int x_begin, y_begin;
	int x_end, y_end;
	int i, j, k;
	
	//init
	for (i=0;i<H;i++) {
		for (j=0;j<W;j++) {
			cost[i][j] = -1;
			if (maze[i][j] == 'S') {
				x_begin = j;
				y_begin = i;
				cost[i][j] = 0;
			} else if (maze[i][j] == 'G') {
				x_end = j;
				y_end = i;
			}
		}
	}
	
	//solve
	solve(x_begin, y_begin);
	
	//path
	while (1) {
		for (k=0;k<4;k++) {
			i = y_end + diff[k][1];
			j = x_end + diff[k][0];
			//bounds
			if (i < 0 || j < 0 || i >= H || j >= W) {
				continue;
			}
			//next
			if (cost[i][j] == cost[y_end][x_end] - 1) {
				y_end = i;
				x_end = j;
				break;
			}
		}
		//start
		if (cost[y_end][x_end] == 0) {
			break;
		}
		maze[y_end][x_end] = '$';
	}
	
	//output
	output_maze();
	
	return 0;
}

output

**************************
*S* *$$$$$               *
*$* *$ * $*************  *
*$*$$$*  $$************  *
*$$$ *    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G  *
*  *  $$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************