bfsの練習

bfs.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <utility>
#include <limits>
#include <functional>
#include <queue>
#include <array>
#include <iomanip>

enum class celltype : long {
  WALL = 0,
  BLANK,
  START,
  GOAL
};

class maze {
  public:
    int nrow;
    int ncol;

    maze(std::string file_name) : nrow(0), ncol(0){
      read(file_name);
    };
    ~maze() {};
    void show(void) const;

    celltype operator ()(int i, int j) const{return this->field[i][j];};
  private:
    std::vector< std::vector<celltype> > field;

    bool read(std::string filename);
    char cellToAscii(celltype v) const;
    celltype asciiToCell(const char c) const;
};

char maze::cellToAscii(celltype v) const{
  char ret = ' ';
  switch(v) {
    case celltype::WALL://WALL
      ret = '#';
      break;
    case celltype::BLANK://BLANK
      ret = ' ';
      break;
    case celltype::START://START
      ret = 'S';
      break;
    case celltype::GOAL://GOAL
      ret = 'G';
      break;
  }
  return ret;
}

celltype maze::asciiToCell(const char c) const{
  celltype ret = celltype::WALL;
  switch(c) {
    case '#':
      ret = celltype::WALL;
      break;
    case 'x':
      ret = celltype::BLANK;
      break;
    case 's':
      ret = celltype::START;
      break;
    case 'g':
      ret = celltype::GOAL;
      break;
  }
  return ret;
}

// 表示機構
void maze::show() const{
  for (auto row : this->field) {
    for (celltype cell : row) {
      std::cout<<cellToAscii(cell);
    }
    std::cout<<std::endl;
  }
}

// mapを読み込む
bool maze::read(std::string filename) {
  std::ifstream ifs(filename);
  if (ifs.fail()) {
    throw std::runtime_error("failed to open a file.") ;
    return false;
  }
  //std::vector< std::vector<celltype> > res;
  std::string line;
  long row = 0;
  while (getline(ifs, line)) {
    std::istringstream iss(line);
    this->field.push_back(std::vector<celltype>());
    for (auto el : line) {
      this->field[row].push_back(asciiToCell(el));
    }
    ++row;
  }
  this->nrow = field.size();
  this->ncol = field[0].size();
  return true;
}

//#####################################################
class mazeSolver {
  public:
    mazeSolver(maze m) : field(m){
      this->memo = std::vector<int>((field.ncol)*(field.nrow));//memo
      std::fill(std::begin(this->memo), std::end(this->memo), -1);
      //std::function<int(int, int)> idx = [&](int y, int x) -> int{return y*field.ncol+x;};
    };
    ~mazeSolver() {};
    int solve();
    void show() const; 
  private:
    maze field;
    std::vector<int> memo;
    //std::function<int(int, int)> idx;

    int idx(int y, int x) const{return y*field.ncol+x;};
    std::pair<int,int> find(celltype ct) const;
};
void mazeSolver::show() const{
  long i = 0;
  for(auto el : memo){
    if(el == std::numeric_limits<int>::max()) {
      std::cout<<std::setw(3)<<"#";
    } else if (el == -1){
      std::cout<<std::setw(3)<<"$";
    } else {
      std::cout<<std::setw(3)<<el;
    }
    if((i+1)%(field.ncol)==0) std::cout<<std::endl;
    i++;
  }
}
int mazeSolver::solve() {
  auto start = find(celltype::START);
  auto goal = find(celltype::GOAL);
  int sx = start.second,
      sy = start.first,
      gx = goal.second,
      gy = goal.first;
  std::array<int, 4> dx = { 0,  0, 1, -1};
  std::array<int, 4> dy = { 1, -1, 0,  0};
  std::queue<std::pair<int,int>> node;
  //start
  int cx = sx,
      cy = sy;
  memo[idx(cy,cx)] = 0;
  node.push(std::make_pair(cx,cy));
  while(node.empty() == false){
    // pop
    std::pair<int, int> cp = node.front();
    node.pop();
    int cx = cp.first;
    int cy = cp.second;
    //隣接を確認する
    for (int i=0; i<4; i++) {
      int nx, ny;//Next X, Next Y
      nx = cx + dx[i];
      ny = cy + dy[i];
      // 距離を増やす
      // memoチェック
      if (memo[idx(ny, nx)] == -1){
        if (field(ny, nx) == celltype::BLANK) {
          memo[idx(ny, nx)] = memo[idx(cy,cx)]+1;
          node.push(std::make_pair(nx, ny));
        } else if (field(ny, nx) == celltype::GOAL) {
          memo[idx(ny,nx)] = memo[idx(cy,cx)]+1;
        } else if (field(ny, nx) == celltype::WALL) {
          memo[idx(ny,nx)] = std::numeric_limits<int>::max();
        }
      }
    }
  }
  return memo[idx(gy, gx)];
}
std::pair<int, int> mazeSolver::find(celltype ct) const{
  for (int i=1;i<this->field.nrow-1;i++) {
    for (int j=1;j<this->field.nrow-1;j++) {
      if (field(i,j) == ct) {
        return std::make_pair(i,j);
      }
    }
  }
  return std::make_pair(-1,-1);
}
//#####################################################

int main() {
  maze m("map.txt");
  m.show();
  mazeSolver slv(m);
  std::cout<<slv.solve()<<std::endl;
  slv.show();
  return 0;
}