読者です 読者をやめる 読者になる 読者になる

SRM439 Div1 250 MazeMaker

C++ TopCoder

迷路関係の問題。上下左右に動けるんじゃなくって、動き方が決まっている。いくつか行けない場所が指定されていて、その中で行くのに一番遠い場所に行くためのステップ数を返せ、というような問題。幅優先。

// BEGIN CUT HERE
// END CUT HERE
// Xの場所は通れない
// なんかジャンプができるらしい

#include <string>
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

class MazeMaker {
public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
	std::set<pair<int, int> > unvisited;
	for(int i = 0; i < (int) maze.size(); i++){ // '.'のところにUNVISITEDのマークを付ける
	  string s = maze.at(i);
	  for(int j = 0; j < (int) s.size(); j++) {
		if (s.at(j) == '.') unvisited.insert(make_pair(i, j));
	  }
	}

	pair<int, int> cur = make_pair(startRow, startCol); // 現在位置
	unvisited.erase(cur);

	int rowMax = (int) maze.size();
	int colMax = (int) maze[0].size();

	int n = (int) moveCol.size();

	queue<pair<int, int> > queue; // 幅優先で次に行けるところを管理

	for(int i = 0; i < n; i++) {
	  int row = cur.first + moveRow[i];
	  int col = cur.second + moveCol[i];
	  if (row >= 0 || row <= rowMax || col >= 0 || col <= colMax) { // 迷路の中にいる
		pair<int, int> nextPos = make_pair(row, col);
		// まだ来てないところだったらqueueに追加
		if (unvisited.find(nextPos) != unvisited.end()) {
		  unvisited.erase(nextPos);
		  queue.push(nextPos); 
		}
	  }		  
	}

	int result = 1;
	while(!unvisited.empty()) {
	  bool flag = false; // 一回も追加されなかったかのflag
	  std::queue<std::pair<int, int> > tmp; // 幅優先で次に行けるところを管理
	  while(!queue.empty()) {
		cur = queue.front(); queue.pop();
		for(int i = 0; i < n; i++) {
		  int row = cur.first + moveRow[i];
		  int col = cur.second + moveCol[i];
		  if (row >= 0 || row <= rowMax || col >= 0 || col <= colMax) { // 迷路の中にいる
			pair<int, int> nextPos = make_pair(row, col);
			// まだ来てないところだったらqueueに追加
			if (unvisited.find(nextPos) != unvisited.end()) {
			  unvisited.erase(nextPos);
			  tmp.push(nextPos); 
			  flag  = true;
			}
		  }
		}
	  }
	  if (!flag) return -1;
	  queue = tmp;
	  result++;
	}
	return result;
  }
  
// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arr0[] = {"...",
 "...",
 "..."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 1; int Arr3[] = {1,0,-1,0}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0,1,0,-1}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arg5 = 3; verify_case(0, Arg5, longestPath(Arg0, Arg1, Arg2, Arg3, Arg4)); }
	void test_case_1() { string Arr0[] = {"...",
 "...",
 "..."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 1; int Arr3[] = {1, 0, -1, 0, 1, 1, -1, -1}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0, 1, 0, -1, 1, -1, 1, -1}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arg5 = 2; verify_case(1, Arg5, longestPath(Arg0, Arg1, Arg2, Arg3, Arg4)); }
	void test_case_2() { string Arr0[] = {"X.X",
 "...",
 "XXX",
 "X.X"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 1; int Arr3[] = {1, 0, -1, 0}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0, 1, 0, -1}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arg5 = -1; verify_case(2, Arg5, longestPath(Arg0, Arg1, Arg2, Arg3, Arg4)); }
	void test_case_3() { string Arr0[] = {".......",
 "X.X.X..",
 "XXX...X",
 "....X..",
 "X....X.",
 "......."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 5; int Arg2 = 0; int Arr3[] = {1, 0, -1, 0,-2, 1}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0, -1, 0, 1, 3, 0}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arg5 = 7; verify_case(3, Arg5, longestPath(Arg0, Arg1, Arg2, Arg3, Arg4)); }
	void test_case_4() { string Arr0[] = {"......."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 0; int Arr3[] = {1, 0, 1, 0, 1, 0}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0, 1, 0, 1, 0, 1}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arg5 = 6; verify_case(4, Arg5, longestPath(Arg0, Arg1, Arg2, Arg3, Arg4)); }
	void test_case_5() { string Arr0[] = {"..X.X.X.X.X.X."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 0; int Arr3[] = {2,0,-2,0}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0,2,0,-2}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arg5 = -1; verify_case(5, Arg5, longestPath(Arg0, Arg1, Arg2, Arg3, Arg4)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main() {
  MazeMaker ___test;
  ___test.run_test(-1);
}

// END CUT HERE