ゴミ箱.net

汚物は消毒

ぼくれべるふぉお

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

スーパーアルゴリズマーを目指す俺としてはチャレンジしないわけにはいかん。
C++を使って書いてみたよ。30分ぐらいかかった。

最短性のチェックまで正しくできたらレベル4らしい。ただ「最短性のチェック」の意味するところがよく分からん。とりあえず仕様は満たした。文句あるか。
とりあえず最短経路は出すようにしたので、俺はレベル2なのか?

ソースはこちら。

#include <stdio.h>

int main(void) {
const int dx[] = {0, -1, 0, 1, 0};
const int dy[] = {0, 0, -1, 0, 1};

const int MAX_WIDTH = 100;
const int MAX_HEIGHT = 100;

char data[MAX_HEIGHT][MAX_WIDTH];

enum Direction {
UNKNOWN,
LEFT,
TOP,
RIGHT,
BOTTOM,
};

enum Direction direction[MAX_HEIGHT][MAX_WIDTH];

int minDistance[MAX_HEIGHT][MAX_WIDTH];

for (int y = 0; y < MAX_HEIGHT; y++) {
data[y][0] = '\0';
}

for (int y = 0; y < MAX_HEIGHT; y++) {
for (int x = 0; x < MAX_WIDTH; x++) {
direction[y][x] = UNKNOWN;
minDistance[y][x] = -1;
}
}

for (int y = 0; y < MAX_HEIGHT; y++) {
if (!fgets(data[y], MAX_WIDTH, stdin)) {
break;
}
}

for (int y = 0; y < MAX_HEIGHT; y++) {
for (int x = 0; x < MAX_WIDTH; x++) {
if (data[y][x] == 'S') {
minDistance[y][x] = 0;
}
}
}

int goalX, goalY;
for (int distance = 0; ; distance++) {
for (int y = 0; y < MAX_HEIGHT; y++) {
if (data[y][0] == '\0') {
break;
}

for (int x = 0; x < MAX_WIDTH; x++) {
if (data[y][x] == '\0') {
break;
}

if (minDistance[y][x] != distance) {
continue;
}

for (int tmpDirection = LEFT; tmpDirection <= BOTTOM; tmpDirection++) {
int tmpX = x + dx[tmpDirection];
int tmpY = y + dy[tmpDirection];
if ((tmpX < 0) || (tmpX >= MAX_WIDTH) || (tmpY < 0) || (tmpY >= MAX_HEIGHT)) {
continue;
}

if (data[tmpY][tmpX] == '*') {
continue;
}

if (minDistance[tmpY][tmpX] == -1) {
minDistance[tmpY][tmpX] = distance + 1;
direction[tmpY][tmpX] = (enum Direction)tmpDirection;
if (data[tmpY][tmpX] == 'G') {
goalX = tmpX;
goalY = tmpY;
goto finish;
}
}
}
}
}
}

finish:
while (true) {
enum Direction tmpDirection = direction[goalY][goalX];
goalX = goalX - dx[tmpDirection];
goalY = goalY - dy[tmpDirection];

if (data[goalY][goalX] == 'S') {
break;
}

data[goalY][goalX] = '$';
}

for (int y = 0; y < MAX_HEIGHT; y++) {
if (data[y][0] == '\0') {
break;
}
printf("%s", data[y]);
}
}


標準入力からパイプ経由でデータを読み込ませると、標準出力に最短経路を吐く。


入力として
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************

を与えると
**************************
*S* *$$$$$ *
*$* *$ * $************* *
*$*$$$* $$************ *
*$$$ * $$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G *
* * $$$ *********** * *
* * ******* * *
* * *
**************************
が得られます。

毎回すべてのセルを走査なんていうタコスケなことをしているが、更新されたセルのセットをC++で管理する仕組みの実装が面倒だっただけだからね!
スポンサーサイト

PageTop

コメント


管理者にだけ表示を許可する