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