前回の記事で作成したターミナル上の迷路をさらに改良して、足立法で、スタートからゴールまでの最短経路を表示させたい。
まず、前回の記事の迷路の壁の数字はただの座標であり、本来は探索中に見つけた情報を格納する配列から値を代入するのが正しい。マイクロマウスの公式試合ではクラシックでは１６×１６の迷路を探索するのであり、そこを変更する必要はないのだが、せっかくなのでプログラム実行時の引数で迷路の大きさを操作できるようにしたい。
さらに壁の情報だけではなく、区画の情報も必要だ。足立法ではマッピングを行うことで最短経路を得られるので、その情報を得る必要がある。
まずは、壁の情報から。引数で変動するような配列の情報は動的配列であるstd::vectorを使うといい。２次元配列なので、宣言は
std::vector< std::vector<int> > kabe;
みたいな感じで行う。これに、
kabe.resize(16);
for (int i; i < 16; i++){
kabe[i].resize(16);
}
とすると、16×１６の２次元配列が出来上がる。今回はシミュレータもかねてこの配列に０か１をランダムで入れる。私はたての壁も横の壁も取得したいので、３次元のベクトルをしようしている。
次に足立法について。まず、全ての部屋の数字を２５５にしてゴール近くの部屋の番号を０にし、その０から一つ増えた１を四方に拡散するように広げる。次に１の周りに２を置く・・・というように機体のいる座標まで繰り返し、最短経路を見つけ出すことができる。今回は壁の有無はあくまでランダムなので、ゴールすることができないことを考慮し、拡散ができないようになるとループを抜けるようにした。
そこから、現在の座標からゴールまで経路を辿ることで、最短のルートを行くことができる。ちょっと工夫して経路を示すように表示してみる。
面倒なので、コードをそのまま貼る。
//meiro.cpp
//g++ meiro.cpp -o meiro
//./meiro 16 16
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>
int row;
int col;
int road;
std::vector<int> car;
std::vector< std::vector<int> > heya;
std::vector< std::vector<int> >::iterator heya_num = heya.begin();
std::vector< std::vector< std::vector<int> > > kabe;
void kabe_rand(){
int r;
int c;
srand(time(NULL));
for (r=0; r<row; r++){
for (c=0; c<col+1; c++){
if (rand()%10>2){
kabe[0][r][c]=10;
}else{
kabe[0][r][c]=11;
}
}
}
for (r=0; r<row+1; r++){
for (c=0; c<col; c++){
if (rand()%10>3){
kabe[1][r][c]=10;
}else{
kabe[1][r][c]=11;
}
}
}
}
void kabe_input(int m, int r, int c){
if(kabe[m][r][c] < 10){
std::cout << kabe[m][r][c];
return;
}else if(m == 0){
if (kabe[m][r][c] == 11){
std::cout << "━━";
}else if (kabe[m][r][c] == 10){
std::cout << " ";
}
return;
}else if(m == 1){
if (kabe[m][r][c] == 11){
std::cout << "┃ ";
}else if (kabe[m][r][c] == 10){
std::cout << " ";
}
return;
}
}
void heya_input(int r, int c){
if(heya[r][c] < 256){
if (heya[r][c] < 100){
if (heya[r][c] < 10){
std::cout << " " << heya[r][c] << " ";
}else{
std::cout << " " << heya[r][c] << " ";
}
}else{
std::cout << heya[r][c] << " ";
}
}else if(heya[r][c] == 256){
std::cout << " ↑ ";
}else if(heya[r][c] == 257){
std::cout << "→→→ ";
}else if(heya[r][c] == 258){
std::cout << " ↓ ";
}else if(heya[r][c] == 259){
std::cout << "←←← ";
}else if(heya[r][c] == 260){
std::cout << " ^ ";
}else if(heya[r][c] == 261){
std::cout << " > ";
}else if(heya[r][c] == 262){
std::cout << " v ";
}else if(heya[r][c] == 263){
std::cout << " < ";
}else if(heya[r][c] == 264){
std::cout << " ┏━ ";
}else if(heya[r][c] == 265){
std::cout << "━┓ ";
}else if(heya[r][c] == 266){
std::cout << " ┗━ ";
}else if(heya[r][c] == 267){
std::cout << "━┛ ";
}
return;
}
void running(){
int length = heya[car[0]][car[1]];
int direction = car[2];
int i;
for (i=0; i<length; i++){
if (car[0] + 1 < row){
if (heya[car[0] + 1][car[1]] < length - i && kabe[1][car[0] + 1][car[1]] == 10){
//部屋の進行 >
if (heya[car[0]][car[1]] == 261){//>
heya[car[0]][car[1]] = 257;//→
}else if (heya[car[0]][car[1]] == 262){//v
heya[car[0]][car[1]] = 266;//┗━
}else if (heya[car[0]][car[1]] == 260){//^
heya[car[0]][car[1]] = 264;//┏━
}
car[0] += 1;
heya[car[0]][car[1]] = 261;
continue;
}
}
if (car[0] - 1 > -1){
if (heya[car[0] - 1][car[1]] < length - i && kabe[1][car[0]][car[1]] == 10){
//部屋の進行 <
if (heya[car[0]][car[1]] == 263){//<
heya[car[0]][car[1]] = 259;
}else if (heya[car[0]][car[1]] == 262){//v
heya[car[0]][car[1]] = 267;
}else if (heya[car[0]][car[1]] == 260){//^
heya[car[0]][car[1]] = 265;
}
car[0] -= 1;
heya[car[0]][car[1]] = 263;
continue;
}
}
if (car[1] + 1 < col){
if (heya[car[0]][car[1] + 1] < length - i && kabe[0][car[0]][car[1] + 1] == 10){
//部屋の進行 v
if (heya[car[0]][car[1]] == 262){//v
heya[car[0]][car[1]] = 258;//
}else if (heya[car[0]][car[1]] == 261){//>
heya[car[0]][car[1]] = 265;//
}else if (heya[car[0]][car[1]] == 263){//<
heya[car[0]][car[1]] = 264;//
}
car[1] += 1;
heya[car[0]][car[1]] = 262;
continue;
}
}
if (car[1] - 1 > -1){
if (heya[car[0]][car[1] - 1] < length - i && kabe[0][car[0]][car[1]] == 10){
//部屋の進行 ^
if (heya[car[0]][car[1]] == 260){//^
heya[car[0]][car[1]] = 256;//↑
}else if (heya[car[0]][car[1]] == 261){//>
heya[car[0]][car[1]] = 267;//━┛
}else if (heya[car[0]][car[1]] == 263){//<
heya[car[0]][car[1]] = 266;//┗━
}
car[1] -= 1;
heya[car[0]][car[1]] = 260;
continue;
}
}
std::cout << "something is wrong : " << i << std::endl;
}
return;
}
void map(){
std::vector< std::vector<int> > pos;
std::vector< std::vector<int> > matrix;
int map_num;
int r;
int c;
int i;
for (;;){
pos.resize(2);
map_num = 0;
for(map_num = 0; map_num<256; map_num++){
pos.clear();
pos.resize(2);
for(c=0; c<col; c++){
for(r=0; r<row; r++){
if (heya[r][c] == map_num){
pos[0].push_back(r);
pos[1].push_back(c);
}
}
}
if (pos[0].size() == pos[1].size()){
/*for(i=0; i<pos[0].size(); i++){
std::cout << pos[0][i] << "," << pos[1][i] << std::endl;
}*/
}
if (pos[0].size()==0){
//std::cout << map_num << std::endl;
if (map_num > road){
road = map_num;
}else{
std::cout << "mapping is done" << std::endl;
return;
}
break;
}else{
matrix.clear();
std::copy(pos.begin(), pos.end(), std::back_inserter(matrix));
}
}
/*
for(i=0; i<matrix[0].size(); i++){
std::cout << matrix[0][i] << "," << matrix[1][i] << std::endl;
}*/
for(i=0; i<matrix[0].size(); i++){
if (matrix[0][i]+1 < row){
if (heya[matrix[0][i] + 1][matrix[1][i]] > map_num && kabe[1][matrix[0][i] + 1][matrix[1][i]] == 10){
heya[matrix[0][i] + 1][matrix[1][i]] = map_num;
if (matrix[0][i] + 1 == car[0] && matrix[1][i] == car[1]){
std::cout << "the root has discovered. the length : " << map_num << std::endl;
running();
return;
}
}
}
if (matrix[0][i]-1 > -1){
if (heya[matrix[0][i] - 1][matrix[1][i]] > map_num && kabe[1][matrix[0][i]][matrix[1][i]] == 10){
heya[matrix[0][i] - 1][matrix[1][i]] = map_num;
if (matrix[0][i] - 1 == car[0] && matrix[1][i] == car[1]){
std::cout << "the root has discovered. the length : " << map_num << std::endl;
running();
return;
}
}
}
if (matrix[1][i]+1 < col){
if (heya[matrix[0][i]][matrix[1][i] + 1] > map_num && kabe[0][matrix[0][i]][matrix[1][i] + 1] == 10){
heya[matrix[0][i]][matrix[1][i] + 1] = map_num;
if (matrix[0][i] == car[0] && matrix[1][i] + 1 == car[1]){
std::cout << "the root has discovered. the length : " << map_num << std::endl;
running();
return;
}
}
}
if (matrix[1][i]-1 > -1){
if (heya[matrix[0][i]][matrix[1][i] - 1] > map_num && kabe[0][matrix[0][i]][matrix[1][i]] == 10){
heya[matrix[0][i]][matrix[1][i] - 1] = map_num;
if (matrix[0][i] == car[0] && matrix[1][i] - 1 == car[1]){
std::cout << "the root has discovered. the length : " << map_num << std::endl;
running();
return;
}
}
}
}
}
return;
}
void meiro(){
int r;
int c;
std::cout << "┏━━";
kabe_input(0,0,0);
std::cout << "━━";
for (r=1; r<row; r++){
std::cout << "┳━━";
kabe_input(0,r,0);
std::cout << "━━";
}
printf("┓\n");
kabe_input(1,0,0);
std::cout << " ";
heya_input(0,0);
for (r=1; r<row; r++){
kabe_input(1,r,0);
std::cout << " ";
heya_input(r,0);
}
kabe_input(1,row,0);
std::cout << std::endl;
for (c=1; c<col; c++){
std::cout << "┣━━";
kabe_input(0,0,c);
std::cout << "━━";
for (r=1; r<row; r++){
std::cout << "╋━━";
kabe_input(0,r,c);
std::cout << "━━";
}
std::cout << "┫" << std::endl;
kabe_input(1,0,c);
std::cout << " ";
heya_input(0,c);
for (r=1; r<row; r++){
kabe_input(1,r,c);
std::cout << " ";
heya_input(r,c);
}
kabe_input(1,row,c);
std::cout << std::endl;
}
std::cout << "┗━━";
kabe_input(0,0,col);
std::cout << "━━";
for (r=1; r<row; r++){
std::cout << "┻━━";
kabe_input(0,r,col);
std::cout << "━━";
}
printf("┛\n");
}
int main(int argc, char* argv[]){
if (argc != 3){
printf("error : number is %d\n",argc);
return 1;
}
row = atoi(argv[1]);
col = atoi(argv[2]);
if (row < 1 || col < 1){
printf("error : number must be more than zero.\n");
return 1;
}
int i;
for(i=1; i<argc; i++){
printf("number %d is %d \n",i,atoi(argv[i]));
}
int r;
int c;
kabe.resize(2);
kabe[0].resize(row);
for (r=0; r<row; r++){
kabe[0][r].resize(col+1);
for (c=0; c<col+1; c++){
kabe[0][r][c] = 0;
}
}
kabe[1].resize(row+1);
for (r=0; r<row+1; r++){
kabe[1][r].resize(col);
for (c=0; c<col; c++){
kabe[1][r][c] = 0;
}
}
heya.resize(row);
for (r=0; r<row; r++){
heya[r].resize(col);
for (c=0; c<col; c++){
heya[r][c] = 255;
}
}
car.resize(3);
car[0] = 0;
car[1] = col - 1;
car[2] = 260;
heya[car[0]][car[1]] = car[2];
heya[7][7]=0;
heya[7][8]=0;
heya[8][7]=0;
heya[8][8]=0;
kabe_rand();
map();
meiro();
}
このコードを貼ってg++ meiro.cpp -o meiroと打って./meiro 16 16と実行すると、迷路が表示される。
もう少し改良の余地があるかもしれない。
