TopCoder: SRM150 DIV2 1000
36130 단어 topcoder
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
(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
0)
{ ".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
3)
{ "..BBB...",
".#BB..#.",
"B.#B.B..",
"B.B.....",
"##.B.B#.",
"#BB.#.B.",
"B..B.BB.",
"#..BB..B",
".B....#." }
Returns: -1
4)
{ ".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
5)
{ ".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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
SRM 574먼저 연결 블록, 왼쪽 또는 오른쪽으로 나누어 다음과 같은 그림을 연결할 수 있다. 다섯 번째 줄을 이어서 세 번째 줄을 하나로 만들 수 있다. 이것은 욕심으로 해결할 수 있다. 그러나 위의 이런 두 번째 줄은 어느...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.