[白俊15683]監視
6342 ワード
監視
監視カメラの監視場所が多ければ多いほど、死角は小さくなると考えられています.
しかしよく考えてみると、Greedyを使用して解くと、同じ位置の量を監視していると思ったら、一方向を選択してナビゲートします.その後,既存のモニタリングビデオと同じ場所を監視すると損失をもたらすため,死角最小化の答えを得るために方法を変更し,すべての方法を探索することにした.
例)
4 4
1 0 0 0
0 0 0 0
0 0 6 4
0 0 0 0
上記の場合、1は東にも南にも同じ監視可能領域があるが、後ろの4の方向が4の方向を決めているため、1の南への監視は死角を最小にする.
したがって,1監視領域を東として特定してナビゲーションを行うと,最適な結果は得られない.
A.方法
監視カメラの監視場所が多ければ多いほど、死角は小さくなると考えられています.
しかしよく考えてみると、Greedyを使用して解くと、同じ位置の量を監視していると思ったら、一方向を選択してナビゲートします.その後,既存のモニタリングビデオと同じ場所を監視すると損失をもたらすため,死角最小化の答えを得るために方法を変更し,すべての方法を探索することにした.
例)
4 4
1 0 0 0
0 0 0 0
0 0 6 4
0 0 0 0
上記の場合、1は東にも南にも同じ監視可能領域があるが、後ろの4の方向が4の方向を決めているため、1の南への監視は死角を最小にする.
したがって,1監視領域を東として特定してナビゲーションを行うと,最適な結果は得られない.
B.実施
C.コード
#include <iostream>
#include <vector>
using namespace std;
int N, M;
int T;
int i, j;
vector<vector<int>> v;
int answer = 99999999;
// goXXXX는 해당 방향으로 빈칸인 경우 -1로 바꿔서 감시되는 영역이라고 표시한다. 벽을 만나면 종료.
void goEast(int x, int y, vector<vector<int>>& v) {
for(int a = y + 1; a < M; a++) {
if(v[x][a] == 0)
v[x][a] = -1;
else if(v[x][a] == 6)
break;
}
}
void goWest(int x, int y, vector<vector<int>>& v) {
for(int a = y - 1; a >= 0; a--) {
if(v[x][a] == 0)
v[x][a] = -1;
else if(v[x][a] == 6)
break;
}
}
void goSouth(int x, int y, vector<vector<int>>& v) {
for(int a = x + 1; a < N; a++) {
if(v[a][y] == 0)
v[a][y] = -1;
else if(v[a][y] == 6)
break;
}
}
void goNorth(int x, int y, vector<vector<int>>& v) {
for(int a = x - 1; a >= 0; a--) {
if(v[a][y] == 0)
v[a][y] = -1;
else if(v[a][y] == 6)
break;
}
}
void solver(int i, vector<vector<int>> tv) {
int a, b;
if(i == M * N) {
int cnt = 0;
for(a = 0; a < N; a++) {
for(b = 0; b < M; b++) {
if(tv[a][b] == 0)
cnt++;
}
}
if(cnt < answer)
answer = cnt;
return;
}
int x = i / M;
int y = i % M;
vector<vector<int>> tv1(tv);
vector<vector<int>> tv2(tv);
vector<vector<int>> tv3(tv);
vector<vector<int>> tv4(tv);
switch(tv[x][y]) {
case 1:
goEast(x, y, tv1);
solver(i + 1, tv1);
goWest(x, y, tv2);
solver(i + 1, tv2);
goSouth(x, y, tv3);
solver(i + 1, tv3);
goNorth(x, y, tv4);
solver(i + 1, tv4);
break;
case 2:
goEast(x, y, tv1);
goWest(x, y, tv1);
solver(i + 1, tv1);
goSouth(x, y, tv2);
goNorth(x, y, tv2);
solver(i + 1, tv2);
break;
case 3:
goNorth(x, y, tv1);
goEast(x, y, tv1);
solver(i + 1, tv1);
goEast(x, y, tv2);
goSouth(x, y, tv2);
solver(i + 1, tv2);
goSouth(x, y, tv3);
goWest(x, y, tv3);
solver(i + 1, tv3);
goWest(x, y, tv4);
goNorth(x, y, tv4);
solver(i + 1, tv4);
break;
case 4:
goEast(x, y, tv1);
goWest(x, y, tv1);
goSouth(x, y, tv1);
solver(i + 1, tv1);
goEast(x, y, tv2);
goWest(x, y, tv2);
goNorth(x, y, tv2);
solver(i + 1, tv2);
goEast(x, y, tv3);
goSouth(x, y, tv3);
goNorth(x, y, tv3);
solver(i + 1, tv3);
goWest(x, y, tv4);
goSouth(x, y, tv4);
goNorth(x, y, tv4);
solver(i + 1, tv4);
break;
case 5:
goEast(x, y, tv1);
goWest(x, y, tv1);
goSouth(x, y, tv1);
goNorth(x, y, tv1);
solver(i + 1, tv1);
break;
default:
solver(i + 1, tv);
break;
}
}
int main() {
//scanf("%d", &T);
T = 1;
for(int tc = 0; tc < T; tc++) {
scanf("%d %d", &N, &M);
v.clear();
v.resize(N);
answer = 99999999;
int tmp;
for(i = 0; i < N; i++) {
for(j = 0; j < M; j++) {
scanf("%d", &tmp);
v[i].push_back(tmp);
}
}
solver(0, v);
printf("%d\n", answer);
}
return 0;
}D.結果
Reference
この問題について([白俊15683]監視), 我々は、より多くの情報をここで見つけました https://velog.io/@pamrk2002/백준-15683감시テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol