Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define INF 987654321
- #define UP 0
- #define RIGHT 1
- #define DOWN 2
- #define LEFT 3
- using namespace std;
- int Y, X, board[9][9];
- int dy[] = { -1,0,1,0 };
- int dx[] = { 0,1,0,-1 };
- int ans;
- vector<pair<int, int> > listCCTV;
- void check(int y, int x, int dir,int idx) {
- if (dir == UP) {
- for (int i = y - 1; i >= 0 ; i--) {
- if (board[i][x] == 6 )
- break;
- else if ((1 <= board[i][x] && board[i][x] <= 5) || board[i][x] >= 7)
- continue;
- board[i][x] = idx+7;
- }
- }
- else if (dir == RIGHT) {
- for (int i = x + 1; i < X; i++) {
- if (board[y][i] == 6 )
- break;
- else if ((1 <= board[y][i] && board[y][i] <= 5) || board[y][i] >= 7)
- continue;
- board[y][i] = idx + 7;
- }
- }
- else if (dir == DOWN) {
- for (int i = y + 1; i < Y; i++) {
- if (board[i][x] == 6 )
- break;
- else if ((1 <= board[i][x] && board[i][x] <= 5) || board[i][x] >= 7)
- continue;
- board[i][x] = idx + 7;
- }
- }
- else if (dir == LEFT) {
- for (int i = x - 1; i >= 0; i--) {
- if (board[y][i] == 6 )
- break;
- else if ((1 <= board[y][i] && board[y][i] <= 5) || board[y][i] >= 7)
- continue;
- board[y][i] = idx + 7;
- }
- }
- }
- void uncheck(int y, int x, int dir, int idx) {
- if (dir == UP) {
- for (int i = y - 1; i >= 0; i--) {
- if (board[i][x] == 6)
- break;
- else if (1 <= board[i][x] && board[i][x] <= 5)
- continue;
- else if (board[i][x]==idx+7)
- board[i][x] = 0;
- }
- }
- else if (dir == RIGHT) {
- for (int i = x + 1; i < X; i++) {
- if (board[y][i] == 6)
- break;
- else if (1 <= board[y][i] && board[y][i] <= 5)
- continue;
- else if (board[y][i] == idx + 7)
- board[y][i] = 0;
- }
- }
- else if (dir == DOWN) {
- for (int i = y + 1; i < Y; i++) {
- if (board[i][x] == 6)
- break;
- else if (1 <= board[i][x] && board[i][x] <= 5)
- continue;
- else if (board[i][x] == idx + 7)
- board[i][x] = 0;
- }
- }
- else if (dir == LEFT) {
- for (int i = x - 1; i >= 0; i--) {
- if (board[y][i] == 6)
- break;
- else if (1 <= board[y][i] && board[y][i] <= 5)
- continue;
- else if (board[y][i] == idx + 7)
- board[y][i] = 0;
- }
- }
- }
- void solve(int idx) {
- if (idx == listCCTV.size()) {
- int ret = 0;
- for (int i = 0; i < Y; i++) {
- for (int j = 0; j < X; j++) {
- if (board[i][j] == 0) {
- ret++;
- }
- }
- }
- if (ans > ret) {
- ans = ret;
- }
- return;
- }
- int y = listCCTV[idx].first;
- int x = listCCTV[idx].second;
- int numCCTV = board[y][x];
- for (int dir = 0; dir < 4; dir++) {
- if (numCCTV == 1) {
- check(y, x, dir,idx);
- solve(idx + 1);
- uncheck(y, x, dir, idx);
- }
- else if (numCCTV == 2) {
- check(y, x, dir, idx);
- check(y, x, (dir + 2) % 4, idx);
- solve(idx + 1);
- uncheck(y, x, dir, idx);
- uncheck(y, x, (dir + 2) % 4, idx);
- }
- else if (numCCTV == 3) {
- check(y, x, dir, idx);
- check(y, x, (dir + 1) % 4, idx);
- solve(idx + 1);
- uncheck(y, x, dir, idx);
- uncheck(y, x, (dir + 1) % 4, idx);
- }
- else if (numCCTV == 4) {
- check(y, x, dir, idx);
- check(y, x, (dir + 1) % 4, idx);
- check(y, x, (dir + 2) % 4, idx);
- solve(idx + 1);
- uncheck(y, x, dir, idx);
- uncheck(y, x, (dir + 1) % 4, idx);
- uncheck(y, x, (dir + 2) % 4, idx);
- }
- else if (numCCTV == 5) {
- check(y, x, dir, idx);
- check(y, x, (dir + 1) % 4, idx);
- check(y, x, (dir + 2) % 4, idx);
- check(y, x, (dir + 3) % 4, idx);
- solve(idx + 1);
- uncheck(y, x, dir, idx);
- uncheck(y, x, (dir + 1) % 4, idx);
- uncheck(y, x, (dir + 2) % 4, idx);
- uncheck(y, x, (dir + 3) % 4, idx);
- }
- }
- }
- int main() {
- scanf("%d %d", &Y, &X);
- ans = INF;
- for (int i = 0; i < Y; i++) {
- for (int j = 0; j < X; j++) {
- scanf("%d", &board[i][j]);
- if (board[i][j] != 6 && board[i][j] != 0)
- listCCTV.push_back(make_pair(i, j));
- }
- }
- solve(0);
- printf("%d\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement