찌로그
[BOJ] 백준 15683번 감시 2020_05_26 C++ 본문
https://www.acmicpc.net/problem/15683
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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 | #include <bits/stdc++.h> using namespace std; #define For(a,b,i) for(int i=a; i<b; i++) typedef pair<int, int> p; const int dy[4] = {-1,1,0,0}; const int dx[4] = {0,0,-1,1}; int n,m,answer=INT_MAX; int og[8][8]; //vector<vector<p>> cams(7); vector<p> cams; void zeros(int maps[8][8]){ int temp =0; For(0,n,i) For(0,m,j) if(maps[i][j] == 0) temp++; // For(0,n,i){ // For(0,m,j){ // if(maps[i][j] == -1) cout << "* " ; // else cout << maps[i][j] << " "; // } // cout << endl; // } // cout << endl; answer = min(answer, temp); } void marking(int maps[8][8], p a, int i){ p c = a; while(1){ int ny = c.first+dy[i], nx = c.second+dx[i]; if(ny >= n || ny<0 || nx >=m || nx<0) break; if(maps[ny][nx] == 6) break; if(maps[ny][nx] == 0) maps[ny][nx] = -1; c.first = ny, c.second = nx; } } void input(){ cin >> n >> m; For(0,n,i){ For(0,m,j){ cin >> og[i][j]; if(og[i][j] != 0 && og[i][j] != 6){ cams.push_back({i,j}); } } } } void dfs(int copied[8][8], int i){ if(i == cams.size()){ zeros(copied); return; } p q = cams[i]; int cat = og[q.first][q.second]; if(cat == 1){ // 4 cases int next[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next[0][0]); marking(next,q,0); dfs(next,i+1); int next2[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next2[0][0]); marking(next2,q,1); dfs(next2,i+1); int next3[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next3[0][0]); marking(next3,q,2); dfs(next3,i+1); int next4[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next4[0][0]); marking(next4,q,3); dfs(next4,i+1); } else if(cat == 2){ // 2 cases int next[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next[0][0]); marking(next,q,0); marking(next,q,1); dfs(next,i+1); int next2[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next2[0][0]); marking(next2,q,2); marking(next2,q,3); dfs(next2,i+1); }else if(cat == 3){ // 4 casses int next[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next[0][0]); marking(next,q,0); marking(next,q,3); dfs(next,i+1); int next2[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next2[0][0]); marking(next2,q,1); marking(next2,q,3); dfs(next2,i+1); int next3[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next3[0][0]); marking(next3,q,1); marking(next3,q,2); dfs(next3,i+1); int next4[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next4[0][0]); marking(next4,q,0); marking(next4,q,2); dfs(next4,i+1); }else if(cat == 4){ // 4 casses int next[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next[0][0]); marking(next,q,0); marking(next,q,2); marking(next,q,3); dfs(next,i+1); int next2[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next2[0][0]); marking(next2,q,1); marking(next2,q,2); marking(next2,q,3); dfs(next2,i+1); int next3[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next3[0][0]); marking(next3,q,0); marking(next3,q,1); marking(next3,q,2); dfs(next3,i+1); int next4[8][8]; copy(&copied[0][0], &copied[0][0]+(8*8), &next4[0][0]); marking(next4,q,0); marking(next4,q,1); marking(next4,q,3); dfs(next4,i+1); }else if(cat == 5){ For(0,4,i) marking(copied, q, i); dfs(copied,i+1); } } void solve(){ dfs(og, 0); cout << answer <<endl; } int main(){ input(); solve(); return 0; } | cs |
'Coding' 카테고리의 다른 글
[프로그래머스] level2 쇠막대기 2020_05_29 Python3 (0) | 2020.05.29 |
---|---|
[프로그래머스] level2 프린터 2020_05_29 Python3 (0) | 2020.05.29 |
[BOJ] 백준 14891번 톱니바퀴 2020_05_22 C++ (0) | 2020.05.22 |
[BOJ] 백준 14890번 경사로 2020_05_22 C++ (0) | 2020.05.22 |
[BOJ] 백준 17825번 주사위 윷놀이 2020_05_21 C++ (0) | 2020.05.21 |
Comments