MASATOの開発日記

人材獲得作戦・４　試験問題

人材獲得作戦・４　試験問題というのがあったのでやってみました。

60分で以下のコードができました。
内訳は以下の通り。

入力ファイルを読み込んでメモリに落とすコード	10分
最小値を検索するコード(関数FindRoot)	29分
最小ルートを$に置き換える関数(関数MapRoot)	10分
空白マップのときの処理時間が長いことに気がついて修正	8分
不要なコード削除、入出力周り整理	3分

入出力周りや、細かいバグで結構時間を取られました。 こういうのを30分以下でできる人は凄いと思います。

コード

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

using namespace std;

int StartX = 0;
int StartY = 0;
int GoalX = 0;
int GoalY = 0;
vector<string> Maze;
vector<basic_string<int> > Answer;

void FindRoot(int x, int y, int level);
void MapRoot(int x, int y);

int main(int argc, char* argv[])
{
  for (size_t y = 0; !cin.eof(); ++y) {
    string line;
    getline(cin, line);
    for (size_t x = 0; x < line.size(); ++x) {
      switch (line[x]) {
      case 'S':
        StartX = x;
        StartY = y;
        break;
      case 'G':
        GoalX = x;
        GoalY = y;
        break;
      }
    }
    basic_string<int> answer(line.size(), 0);
    Maze.push_back(line);
    Answer.push_back(answer);
  }

  FindRoot(StartX, StartY, 1);
  MapRoot(GoalX, GoalY);

  for (size_t y = 0; y < Maze.size(); y++) {
    cout << Maze[y] << endl;
  }
  return 0;
}

void FindRoot(int x, int y, int level)
{
  Answer[y][x] = 1;
  for (int level = 1, goal = 0; !goal; ++level) {
    for (size_t y = 0; y < Maze.size(); ++y) {
      for (size_t x = 0; x < Maze[y].size(); ++x) {
        if (Answer[y][x] == level) {
          for (int xp = -1, yp = 0, i = 0; i < 4; xp += yp, yp = xp - yp, xp = yp - xp, ++i) {
            char c = Maze[y + yp][x + xp];
            int a = Answer[y + yp][x + xp];
            if (c != '*' && (a == 0 || level < a)) {
              Answer[y + yp][x + xp] = level + 1;
              if (x + xp == GoalX && y + yp == GoalY) {
                goal = 1;
              }
            }
          }
        }
      }
    }
  }
}

void MapRoot(int x, int y)
{
  int a = Answer[y][x];
  for (int xp = -1, yp = 0, i = 0; i < 4; xp += yp, yp = xp - yp, xp = yp - xp, ++i) {
    if (x + xp == StartX && y + yp == StartY) {
      break;
    }
    int b = Answer[y + yp][x + xp];
    if (Answer[y + yp][x + xp] == a - 1) {
      Maze[y + yp][x + xp] = '$';
      MapRoot(x + xp, y + yp);
      break;
    }
  }
}

関数とか使わなくてもできましたね。

出力例

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

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

投稿者 MASATO : 2010年01月11日 16:41 | トラックバック