迷路探索

人材獲得作戦・４　試験問題ほかの迷路探索を解いてみた。BFS知らなかったので調べてから。

#include <stdio.h>
#include <vector>
#include <queue>

struct Pos {
    int x, y;
};

struct MValue {
    int d;
    bool visit;
};

struct Map {
    int width, height;
    std::vector<std::vector<struct MValue> > data;
    struct Pos start, gole;
};

typedef std::vector<struct Pos> PosList;

void Open(struct Map *map, char *name)
{
    FILE *fp;
    int r;
    int y = 0;
        
    fp = fopen(name, "r");
    if (fp == NULL) return;
    
    while ((r = getc(fp)) != EOF) {
	map->data.push_back(std::vector<struct MValue>());
	int x = 0;
	while (r != '\n') {
	    if (r == 'S') {
		map->start.x = x;
		map->start.y = y;
	    } else if (r == 'G') {
		map->gole.x = x;
		map->gole.y = y;
	    }
	    struct MValue v = {r, false};
	    map->data.back().push_back(v);
	    x++;
	    r = getc(fp);
	}
	y++;
    }
    map->width  = map->data[0].size();
    map->height = map->data.size();
    fclose(fp);
}    

void Print(struct Map *map, char *name)
{
    FILE *fp = fopen(name, "w");

    if (fp == NULL) return;
    
    for (int y = 0; y < map->height; y++) {
	for (int x = 0; x < map->width; x++) {
	    fprintf(fp, "%c", map->data[y][x].d);
	}
	fprintf(fp, "\n");
    }
    fclose(fp);
}

bool IsWall(struct Map *map, int x, int y)
{
    if (0 > x || x >= map->width || 0 > y || y >= map->height) return true;
    return (map->data[y][x].d == '*') ? true : false;
}

void setPos(struct Map *map, 
	    std::queue<PosList> &que,
	    PosList &v,
	    int x, int y)
{
    if (map->data[y][x].visit) return;
    
    PosList t = v;
    struct Pos p = {x, y};
    t.push_back(p);
    que.push(t);
    
    map->data[y][x].visit = true;
}    

void Check(struct Map *map)
{
    std::queue<PosList>que;
    
    PosList v;
    struct Pos p = {map->start.x, map->start.y };
    
    v.push_back(p);
    que.push(v);
    
    while (!que.empty()) {
	PosList v = que.front();
	que.pop();
	
	int x = v.at(v.size() - 1).x;
	int y = v.at(v.size() - 1).y;
	
	if (x == map->gole.x && y == map->gole.y) {
	    for (int j = 1; j < v.size() - 1; j++) {
		int x = v.at(j).x;
		int y = v.at(j).y;
		map->data[y][x].d = '$';
	    }
　　　　　　return;
	}
	if (!IsWall(map, x + 1, y)) {
	    setPos(map, que, v, x + 1, y);
	}
	if (!IsWall(map, x - 1, y)) {
	    setPos(map, que, v, x - 1, y);
	}
	if (!IsWall(map, x, y + 1)) {
	    setPos(map, que, v, x, y + 1);
	}
	if (!IsWall(map, x, y - 1)) {
	    setPos(map, que, v, x, y - 1);
	}
    }
}

int main(int argc, char **argv)
{
    struct Map map;
    
    Open(&map, "in.txt");
    Check(&map);
    Print(&map, "out.txt");
    return 0;
}    

in.txt

**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

out.txt

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