迷路を解かせてみる その1
その2以降があるかは謎。迷路を解かせるのが微妙に流行っていたみたいなので。
晒すレベルでもないコードですが、とりあえず迷路でこの解き方はなかったですね。ごめんなさい。
入力部分が書くの面倒になったので直接書いてしまいました。
一応DP使うバージョンとマルチスレッド並列化までは書こうかなあと思ってるけどやるかは不明。
#include <stdio.h> #include <stdlib.h> /*ここから入力*/ char field[13][27] ={"**************************", "*S* * *", "* * * * ************* *", "* * * ************ *", "* * *", "************** ***********", "* *", "** ***********************", "* * G *", "* * *********** * *", "* * ******* * *", "* * *", "**************************"}; int sx = 1; int sy = 1; int gx = 22; int gy = 8; /*ここまで入力*/ enum dir{NONE, UP, DOWN, LEFT, RIGHT}; void print_field(){ for(int i=0; i<13; i++){ printf("%s\n", field[i]); } } int search(int x, int y, int len, int limit, dir prev){ int ret; if(x == gx && y == gy) return 1; if(abs(x-gx)+abs(y-gy)+len>limit) return 0; if(prev != DOWN && field[y-1][x] != '*'){ ret = search(x,y-1,len+1,limit,UP); if(ret == 1){ if(x!=sx || y!=sy) field[y][x] = '$'; return 1; } } if(prev != UP && field[y+1][x] != '*'){ ret = search(x,y+1,len+1,limit,DOWN); if(ret == 1){ if(x!=sx || y!=sy) field[y][x] = '$'; return 1; } } if(prev != RIGHT && field[y][x-1] != '*'){ ret = search(x-1,y,len+1,limit,LEFT); if(ret == 1){ if(x!=sx || y!=sy) field[y][x] = '$'; return 1; } } if(prev != LEFT && field[y][x+1] != '*'){ ret = search(x+1,y,len+1,limit,RIGHT); if(ret == 1){ if(x!=sx || y!=sy) field[y][x] = '$'; return 1; } } return 0; } int main(int argc, char **argv){ print_field(); int startlimit = abs(sx-gx)+abs(sy-gy); for(int i=startlimit; ; i++){ printf("%d\n", i); if(search(sx,sy,0,i,NONE) == 1) break; } print_field(); }