コーディングスキル判定

C/C++ Programming

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほかの問題にたどり着いたので、考えてみた。2時間弱かかったのは、やっぱり最近、コード書いてる量が少ないせいか。

#include <iostream>
#include <cstdio>
#include <fstream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

class Maze {
private:
  vector<int> data;
  vector<int> cost;
  int start;
  int goal;
  int width;
  int height;

  inline int index(int x, int y) const { return x+y*width; }
  inline pair<int, int> coord(int index) {
    return make_pair(index%width, index/width);
  }
	
public:
  Maze() : start(-1), goal(-1), width(-1), height(-1) {}

  void load(string filename) {
    ifstream is(filename.c_str());
    string buf;
    int line = 0;
    while(!is.eof()) {
      getline(is, buf);
      if (width < 0) {
        width = (int)buf.size();
      }
      for(int i = 0; i < buf.size(); ++i) {
        data.push_back(buf[i]);
        if (buf[i] == 'S') start = index(i, line);
        if (buf[i] == 'G') goal = index(i, line);
      }
      ++line;
    }
    height = line;
    cost.resize(width*height);
  }

  void find_path() {
    queue<pair<int, int> > q;
    fill(cost.begin(), cost.end(), height*width);
    q.push(make_pair(start, 0));

    while(!q.empty()) {
      int ind = q.front().first;
      int c = q.front().second;
      q.pop();

      if (data[ind] == '*') continue;
      if (cost[ind] <= c) continue;
      if (ind == goal) {
        if (c < cost[goal]) cost[goal] = c;
        continue;
      }

      pair<int, int> p = coord(ind);
      int x = p.first;
      int y = p.second;
      cost[ind] = c;
      if (x > 0)        q.push(make_pair(ind-1, c+1));
      if (y > 0)        q.push(make_pair(ind-width, c+1));
      if (y < height-1) q.push(make_pair(ind+width, c+1));
      if (x < width-1)  q.push(make_pair(ind+1, c+1));
    }

    printf("goal cost: %d\n", cost[goal]);
  }

  void mark_path() {
    queue<int> q;
    int ind = goal;
    while (ind != start) {
      if (data[ind] == ' ') data[ind] = '$';
      pair<int, int> p = coord(ind);
      int x = p.first;
      int y = p.second;
      int c = cost[ind];
      if (x > 0 && cost[ind-1] == c-1)                  ind -= 1;
      else if (y > 0 && cost[ind-width] == c-1)         ind -= width;
      else if (y < height-1 && cost[ind+width] == c-1)  ind += width;
      else if (x < width-1 && cost[ind+1] == c-1)       ind += 1;
      else {
        cerr << "Found no path." << endl;
        return;
      }
    }
  }

  void print() {
    for(int y = 0; y < height; ++y) {
      for(int x = 0; x < width; ++x) {
        cout << (char)data[index(x,y)];
      }
      cout << endl;
    }
  }

  void print_cost() {
    for(int y = 0; y < height; ++y) {
      for(int x = 0; x < width; ++x) {
        if (cost[index(x,y)] < width*height)
          printf("|%2d", cost[index(x,y)]);
        else
          cout << "|  ";
      }
      cout << '|' << endl;
    }
  }

  void description() {
    printf("Width %d, Height %d\n", width, height);
    pair<int, int> p = coord(start);
    pair<int, int> q = coord(goal);
    printf("Start (%d, %d), Goal (%d, %d)\n", p.first, p.second,
           q.first, q.second);
  }
};


int main(int argc, char** argv) {
  Maze maze;
  maze.load("maze.txt");
  maze.description();
  maze.find_path();
  maze.print_cost();
  maze.mark_path();
  maze.print();
}

実行結果。

Width 26, Height 14
Start (1, 1), Goal (22, 8)
goal cost: 60


    

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    

    

      
     0
      
     8
      
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
      
    

    

      
     1
      
     7
      
     9
    10
      
    14
    15
      
      
      
      
      
      
      
      
      
      
      
      
      
    29
    30
      
    

    

      
     2
      
     6
     7
     8
      
    16
    15
    16
    17
      
      
      
      
      
      
      
      
      
      
      
      
    30
    31
      
    

    

      
     3
     4
     5
     6
      
    18
    17
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
      
    

    

      
      
      
      
      
      
      
      
      
      
      
      
      
      
    23
      
      
      
      
      
      
      
      
      
      
      
    

    

      
    37
    36
    35
    34
    33
    32
    31
    30
    29
    28
    27
    26
    25
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
      
    

    

      
      
    37
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    

    

      
    39
    38
    39
    40
    41
    42
      
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    65
    66
      
    

    

      
    40
    39
      
    41
    42
    43
    44
    45
    46
      
      
      
      
      
      
      
      
      
      
      
    60
      
    64
    65
      
    

    

      
    41
    40
    41
    42
      
    44
    45
    46
    47
    48
    49
    50
    51
      
      
      
      
      
      
      
    61
      
    63
    64
      
    

    

      
    42
    41
    42
    43
    44
    45
    46
      
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
      
    

    

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    

    

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    


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

調べてみると A* というアルゴリズムがあるらしい。こういうのをやっているとアルゴリズムについても色々調べたくなる。