<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)
PS/Topcoder training2018. 7. 3. 00:55
### 전체탐색 ###
### SRM425 Div2 Level2 ###
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <vector> using namespace std; int visited[50][50]; int dr[]={0, 0, 1, -1}; int dc[]={1, -1, 0, 0}; // E W S N int stack[20]; class CrazyBot { public: int n; int dir[4]; double ans; void dfs(int cnt, int r, int c) { if(cnt == n) { double tmp=1.0; for(int i=0; i<n; i++) { tmp *= (double)dir[stack[i]]/100; } ans += tmp; return ; } visited[r][c] = 1; for(int k=0; k<4; k++) { int nr = r+dr[k]; int nc = c+dc[k]; if(!visited[nr][nc]) { stack[cnt] = k; dfs(cnt+1, nr, nc); } } visited[r][c] = 0; } double getProbability(int n, int east, int west, int south, int north) { this->n = n; dir[0] = east; dir[1] = west; dir[2] = south; dir[3] = north; ans = 0; dfs(0, 25, 25); return ans; } }; | cs |
>> n의 최대값이 14이므로 50x50 개의 판을 가정하고 그의 가운데인 (25,25)에서 로봇이 이동하기 시작한다고 생각하였다.
>> 성공적으로 보행할 확률은 이동할 수 있는 모든 경우의 수에 해당하는 확룰을 더하면 된다.
'PS > Topcoder training' 카테고리의 다른 글
| <8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls) (0) | 2018.07.14 |
|---|---|
| <7-5> DP - 악수 (HandShaking) (0) | 2018.07.04 |
| <5-4> 전체탐색 - 회문 (ThePalindrome) (0) | 2018.07.01 |
| <7-4> DP - 킹 나이트 체스 (ChessMetric) (0) | 2018.07.01 |
| <7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors) (0) | 2018.07.01 |
<5-4> 전체탐색 - 회문 (ThePalindrome)
PS/Topcoder training2018. 7. 1. 21:39
### 전체탐색 ###
### SRM428 Div2 Level 1 ###
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <string> using namespace std; class ThePalindrome { public: bool isP(char *str, int s, int e) { if(s >= e) return 1; return str[s]==str[e] ? isP(str, s+1, e-1) : 0; } int find(string s) { char str[101]={0}; int size = s.size(); for(int i=0; i<size; i++) str[i] = s[i]; for(int i=0; i<size; i++) { if(isP(str, 0, size-1+i)) return size+i; for(int j=0; j<=i; j++) { str[size+i-j] = str[j]; } } return size*2-1; } }; | cs |
'PS > Topcoder training' 카테고리의 다른 글
| <7-5> DP - 악수 (HandShaking) (0) | 2018.07.04 |
|---|---|
| <5-7> 전체탐색 - 고장난 로봇 (CrazyBot) (0) | 2018.07.03 |
| <7-4> DP - 킹 나이트 체스 (ChessMetric) (0) | 2018.07.01 |
| <7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors) (0) | 2018.07.01 |
| <7-2> DP - 회사 조직과 급여 (CorporationSalary) (0) | 2018.07.01 |
<7-4> DP - 킹 나이트 체스 (ChessMetric)
PS/Topcoder training2018. 7. 1. 15:09
### DP ###
### TopCoder Collegiate Challenge 2003 Round 4 Div 1 Level 1 ###
<소스코드>
- d[r][c][rest] : (r, c) 에서 (er, ec) 까지 rest 번만에 갈 수 있는 방법의 수
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include <vector> #include <cstring> using namespace std; int n, er, ec; int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1, -2, -2, -1, 1, 2, 2, 1, -1}; int dc[] = {1, 0, -1, 1, -1, 1, 0, -1, 1, -1, -2, -2, -1, 1, 2, 2}; long long d[101][101][51]; bool safe(int r, int c) { return (0 <= r && r < n) && (0 <= c && c < n); } long long solve(int r, int c, int rest) { long long *ret = &d[r][c][rest]; if(rest == 0) { if(r == er && c == ec) return 1LL; return 0LL; } if(*ret != -1) return *ret; *ret = 0LL; for(int k=0; k<16; k++) { int nr = r+dr[k]; int nc = c+dc[k]; if(safe(nr, nc)) { *ret += solve(nr, nc, rest-1); } } return *ret; } class ChessMetric { public: long long howMany(int size, vector<int> start, vector<int> end, int numMoves) { int sr = start[0]; int sc = start[1]; er = end[0]; ec = end[1]; n = size; memset(d, -1, sizeof(d)); return solve(sr, sc, numMoves); } }; | cs |
'PS > Topcoder training' 카테고리의 다른 글
| <7-5> DP - 악수 (HandShaking) (0) | 2018.07.04 |
|---|---|
| <5-7> 전체탐색 - 고장난 로봇 (CrazyBot) (0) | 2018.07.03 |
| <5-4> 전체탐색 - 회문 (ThePalindrome) (0) | 2018.07.01 |
| <7-3> DP - 나쁜 이웃집 사람들 (BadNeighbors) (0) | 2018.07.01 |
| <7-2> DP - 회사 조직과 급여 (CorporationSalary) (0) | 2018.07.01 |
