SRM458 の medium を考えていたんですが行き詰まってしまったので, 息抜きに最近話題のこの問題をやってみました.

人材獲得作戦・４　試験問題ほか: 人生を書き換える者すらいた。

2次元グリッド状の迷路と, スタート地点ゴール地点が与えられるので, スタートからゴールへの最短経路を求めよという問題. ただのbfsです.

時間を測ってみたんですが, 29分もかかってしまっていました. bfsという何度も書いてきたアルゴリズムでこれというのは遅すぎです. 問題文は日本語なのですぐに理解できたし, 方針もすぐにたったので, ボトルネックは実際に書く段階です. まずはデータの入力の部分. ふだんSRMばっかりやっているせいで, ここを書くのに時間をとられました. 次はbfsやループのコード. もう同じことをいままで何度も書いてきているので, いい加減テンプレ化してスピードアップすべきです. またこういう二次元のbfsでよくpairを使うんですが, 値の出し入れが面倒なのでなんとかしたいです. あとは条件のandとorを間違えたり, ループの境界を間違えたりなどがありました.

あと最短性のチェックというのはよくわからなかったのでスルーしました. これに関してはkinabaさんの記事が面白かったです.

d.y.d.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

vector  run(vector  input)
{
  vector  ret = input;
  queue int, int> > > q;
  int visited[input.size()][input[0].size()];
  int startx = 0, starty = 0, goalx = 0, goaly = 0;
  int dirx[4] = {1, 0, -1, 0};
  int diry[4] = {0, 1, 0, -1};
  vector int, int> > path;
  memset(visited, 0, sizeof(visited));

  for (int i=0; ifor (int j=0; j0].size(); j++)
      if (input[i][j] == 'S')
        startx = i, starty = j;
      else if (input[i][j] == 'G')
        goalx = i, goaly = j;

  q.push(vector int, int> > (1, make_pair(startx, starty)));

  while (!q.empty()) {
    vector int, int> > cur = q.front();
    q.pop();
    int curx = cur[cur.size()-1].first, cury = cur[cur.size()-1].second;
    visited[curx][cury] = 1;

    if (curx == goalx && cury == goaly) {
      path = cur;
      break;
    }

    for (int i=0; i<4; i++) {
      int nextx = curx + dirx[i];
      int nexty = cury + diry[i];

      if (0 <= nextx && nextx < input.size() && 0 <= nexty && nexty < input[0].size() &&
          visited[nextx][nexty] == 0 && (input[nextx][nexty] != '*' && input[nextx][nexty] != 'S')) {
        vector int, int> > tmp = cur;
        tmp.push_back(make_pair(nextx, nexty));
        q.push(tmp);
        visited[nextx][nexty] = 1;
      }
    }
  }

  for (int i=0; i'$';

  return ret;
}

int main(int argc, char **argv) {
  if (argc != 2) {
    cout << "Usage " << argv[0] << " \n";
    return 0;
  }

  ifstream file (argv[1]);
  string line;
  vector  input, result;

  while (!file.eof()) {
    getline(file, line);
    input.push_back(line);
  }

  result = run(input);

  for (int i=0; ifor (int j=0; j0].size(); j++)
      cout << result[i][j];
    cout << endl;
  }

  return 0;
}