TopCoder: SRM150 DIV2 1000

Problem Statement

You are given a rectangular map in which each space is marked with one of three characters: '.' (open), 'B' (a brick), or '#' (an indestructible block). Walls made of indestructible blocks surround the field on all sides, but are not shown on the map. A ball is bouncing around this map, destroying bricks, and your task is determine how long it takes the ball to destroy all the bricks. The top left space of the map is always open, and this is where the ball begins. More specifically, the ball begins at time 0 in the middle of the top edge of this space (see the diagram in Example 0). The ball is traveling diagonally down and to the right at a speed of half a meter per second vertically, and half a meter per second horizontally. Each space is 1 meter square, so the ball crosses half a space vertically and half a space horizontally each second. Whenever the ball strikes the edge of an obstacle--either a brick or an indestructible block--it bounces off at an angle perpendicular to its incoming path. The ball will never hit two obstacles simultaneously. Whenever the ball bounces off a brick, the brick is destroyed and removed from the map. Your method should return the time at which the last brick is destroyed. If one or more bricks will never be destroyed, return -1.

Definition

Class:
BrickByBrick
Method:
timeToClear
Parameters:
vector
Returns:
int
Method signature:
int timeToClear(vector map)
(be sure your method is public)

Constraints

-
map contains between 1 and 15 elements, inclusive.
-
All elements of map contain the same number of characters (between 1 and 15, inclusive).
-
All elements of map contain only the characters '.', 'B', and '#'.
-
The top left corner of map (that is, the first character of the first element) is '.'.
-
map contains at least one 'B'.

Examples

{ ".B",

  "BB" }

Returns: 6

The following diagram illustrates the path of the ball.

     __0________

    | / \ |     |

    |/   \|     |

    3  .  1  B  |

    |\   /|\    |

    | \ / | \   |

    |--2--|--6--|

    |     |     |

    |     |     |

    |  B  |  B  |

    |     |     |

    |_____|_____|

The ball begins at point 0, traveling down and to the right. It bounces off the first brick at time 1, and off the second brick at time 2. At time 3, it bounces off the left wall, and at time 4 it bounces off the upper wall at the same place it started. At time 6, the ball destroys the third and final brick, so the method returns 6.
1)

{ ".BB",

  "BBB",

  "BBB" }

Returns: -1

The ball will never hit the brick in the bottom right corner.
2)

{ "......B",

  "###.###",

  "B.....B" }

Returns: 35

{ "..BBB...",

  ".#BB..#.",

  "B.#B.B..",

  "B.B.....",

  "##.B.B#.",

  "#BB.#.B.",

  "B..B.BB.",

  "#..BB..B",

  ".B....#." }

Returns: -1

{ ".BB..BBB.B...",

  "B.B...B..BB..",

  "#B...B#B.....",

  "B#B.B##...##B",

  "BB.B#.B##B.B#",

  "B.B#.BBB.BB#B",

  "B#BBB##.#B#B.",

  "B#BB.BBB#BB.#" }

Returns: 3912

{ ".BBBBBBBBBBBBBB",

  "##############B",

  "BBBBBBBBBBBBBBB",

  "B##############",

  "BBBBBBBBBBBBBBB",

  "##############B",

  "BBBBBBBBBBBBBBB",

  "B##############",

  "BBBBBBBBBBBBBBB",

  "##############B",

  "BBBBBBBBBBBBBBB",

  "B##############",

  "BBBBBBBBBBBBBBB",

  "##############B",

  "BBBBBBBBBBBBBBB" }

Returns: 31753

이 문제는 풀지 못했으니 시뮬레이션 문제라고 할 수 있겠지. 무슨 알고리즘도 없지만 늘 틀린다.

  1 // BEGIN CUT HERE

  2 

  3 // END CUT HERE

  4 #include <functional>

  5 #include <algorithm>

  6 #include <stdexcept>

  7 #include <iostream>

  8 #include <sstream>

  9 #include <fstream>

 10 #include <iomanip>

 11 #include <cstdlib>

 12 #include <cstring>

 13 #include <utility>

 14 #include <cctype>

 15 #include <vector>

 16 #include <string>

 17 #include <bitset>

 18 #include <queue>

 19 #include <stack>

 20 #include <ctime>

 21 #include <list>

 22 #include <map>

 23 #include <set>

 24 #include <math.h>

 25 

 26 using namespace std;

 27 

 28 #define pb push_back

 29 #define INF 100000000000

 30 #define L(s) (int)((s).size())

 31 #define FOR(i,a,b) for (int _n(b), i(a); i<=_n; i++)

 32 #define rep(i,n) FOR(i,1,(n))

 33 #define rept(i,n) FOR(i,0,(n)-1)

 34 #define rept2(i, m, j, n) FOR(i, 0, (m)-1) FOR(j, 0, (n)-1)

 35 #define rep2(i, m, j, n) FOR(i, 1, (m)) FOR(j, 1, (n))

 36 #define C(a) memset((a), 0, sizeof(a))

 37 #define ll long long

 38 #define VI vector<int>

 39 #define ppb pop_back

 40 #define mp make_pair

 41 #define MOD 1000000007

 42 int toInt(string s){ istringstream sin(s); int t; sin>>t;return t;}

 43 

 44 class BrickByBrick

 45 {

 46         public:

 47         struct node {

 48             int x;

 49             int y;

 50             node(int a, int b) : x(a), y(b) {}

 51             node() : x(0), y(0) {}

 52         };

 53         int timeToClear(vector <string> map)

 54         {

 55             int count = 0;

 56             rept2(i, L(map), j, L(map[0]))

 57                 if (map[i][j] == 'B') count++;

 58             node pos(0, 1);

 59             int dir[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

 60             int curdir = 0;

 61             int time = 0;

 62             int m = L(map);

 63             int n = L(map[0]);

 64             int pretime = 0;

 65             while (count > 0) {

 66                 pos.x += dir[curdir][0];

 67                 pos.y += dir[curdir][1];

 68                 time++;

 69                 if (pos.x == m*2 || pos.y == 2*n || pos.x == 0 || pos.y == 0 || map[pos.x/2][pos.y/2] == '#') {

 70                     if (pos.x%2 == 0) {

 71                         if (curdir%2 == 0) curdir = (curdir+3)%4;

 72                         else curdir = (curdir+1)%4;

 73                     }

 74                     if (pos.y%2 == 0) {

 75                         if (curdir%2 == 0) curdir = (curdir+1)%4;

 76                         else curdir = (curdir+3)%4;

 77                     }

 78                 }

 79                 if (map[pos.x/2][pos.y/2] == 'B') {

 80                     map[pos.x/2][pos.y/2] = '.';

 81                     count--;

 82                     if (pos.x%2 == 0) {

 83                         if (curdir%2 == 0) curdir = (curdir+3)%4;

 84                         else curdir = (curdir+1)%4;

 85                     }

 86                     if (pos.y%2 == 0) {

 87                         if (curdir%2 == 0) curdir = (curdir+1)%4;

 88                         else curdir = (curdir+3)%4;

 89                     }

 90                     pretime = time;

 91                     continue;

 92                 }

 93                 if (time - pretime > 4*m*n) return -1;

 94             }

 95             return time;

 96         }

 97 

 98 // BEGIN CUT HERE

 99     public:

100     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(); }

101     private:

102     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(); }

103     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; } }

104     void test_case_0() { string Arr0[] = { ".B",

105   "BB" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 6; verify_case(0, Arg1, timeToClear(Arg0)); }

106     void test_case_1() { string Arr0[] = { ".BB",

107   "BBB",

108   "BBB" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = -1; verify_case(1, Arg1, timeToClear(Arg0)); }

109     void test_case_2() { string Arr0[] = { "......B",

110   "###.###",

111   "B.....B" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 35; verify_case(2, Arg1, timeToClear(Arg0)); }

112     void test_case_3() { string Arr0[] = { "..BBB...",

113   ".#BB..#.",

114   "B.#B.B..",

115   "B.B.....",

116   "##.B.B#.",

117   "#BB.#.B.",

118   "B..B.BB.",

119   "#..BB..B",

120   ".B....#." }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = -1; verify_case(3, Arg1, timeToClear(Arg0)); }

121     void test_case_4() { string Arr0[] = { ".BB..BBB.B...",

122   "B.B...B..BB..",

123   "#B...B#B.....",

124   "B#B.B##...##B",

125   "BB.B#.B##B.B#",

126   "B.B#.BBB.BB#B",

127   "B#BBB##.#B#B.",

128   "B#BB.BBB#BB.#" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3912; verify_case(4, Arg1, timeToClear(Arg0)); }

129     void test_case_5() { string Arr0[] = { ".BBBBBBBBBBBBBB",

130   "##############B",

131   "BBBBBBBBBBBBBBB",

132   "B##############",

133   "BBBBBBBBBBBBBBB",

134   "##############B",

135   "BBBBBBBBBBBBBBB",

136   "B##############",

137   "BBBBBBBBBBBBBBB",

138   "##############B",

139   "BBBBBBBBBBBBBBB",

140   "B##############",

141   "BBBBBBBBBBBBBBB",

142   "##############B",

143   "BBBBBBBBBBBBBBB" }; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 31753; verify_case(5, Arg1, timeToClear(Arg0)); }

144 

145 // END CUT HERE

146 

147 };

148 // BEGIN CUT HERE

149 int main()

150 {

151         BrickByBrick ___test;

152         ___test.run_test(-1);

153         return 0;

154 }

155 // END CUT HERE

TopCoder: SRM150 DIV2 1000

Problem Statement

Definition

Constraints

Examples

좋은 웹페이지 즐겨찾기