■http://anond.hatelabo.jp/20100114003544

34分

現役のときに比べて腕が鈍ってるなあ

ソースは汚いよ

同じところを二回訪れないことに注意して、次の状態をキューに入れていけばいいだけ

隣は距離1なのでただのFIFOでいい

重み付きのグラフならpriority queueを使う

dequeなんちゃらの前までが入力で、while の中が重要なコード

答えはSとGも塗り潰しちゃったのを出力してる

サンプルの入力で最短距離であることを確認してる

増田できれいにC++を出力するにはどうすればいいんだろう？

#include <map&gt;
#include <string&gt;
#include <iostream&gt;
#include <vector&gt;
#include <iterator&gt;
#include <deque&gt;
#include <set&gt;

using namespace std;
typedef pair<int, int&gt; P;

int dir_x[] = {0,1, -1, 0};
int dir_y[] = {1, 0, 0, -1};

int main() {
  string line;
  vector<string&gt; input;

  while (getline(cin, line)) {
    input.push_back(line);
  }
  const int X = input.size();
  const int Y = input.begin()-&gt;size();

  vector<P&gt; start;
  P goal;
  for (int i = 0; i < X; i++) {
    for (int j = 0; j < Y; j++) {
      if (input[i][j] == 'S') {
        start.push_back(P(i, j));
      }
      else if (input[i][j] == 'G') {
        goal = P(i, j);
      }
    }
  }

  deque<vector<P&gt; &gt; Q;
  set<P&gt; visited;
  Q.push_back(start);

  while (!Q.empty()) {
    vector<P&gt; p = Q.front();
    Q.pop_front();

    if (visited.find(p.back()) != visited.end()) { continue; }
    visited.insert(p.back());

    if (p.back() == goal) {
      for (int i = 0; i < p.size(); i++) {
        input[p[i].first][p[i].second] = '$';
      }
      copy(input.begin(), input.end(), ostream_iterator<string&gt;(cout, "\n"));
      break;
    }

    for (int i = 0; i < 4; i++) {
      P next = P(p.back().first + dir_x[i], p.back().second + dir_y[i]);
      if (input[next.first][next.second] == '*') { continue; }
      vector<P&gt; new_state(p.begin(), p.end());
      new_state.push_back(next);
      Q.push_back(new_state);
    }
  }
  return 0;
}

Permalink | 記事への反応(1) | 02:25

ツイートシェア