#include #include using namespace std; int n, m, cnt_cctv, cnt_scan, cnt_wall; tuple cctv[10]; // type, x, y int scanR(vector> &board, int x, int y) { int cnt = 0; for (int i = y + 1; i < m; i++) { if (board[x][i] == 0) { board[x][i] = 11; // scan cnt++; continue; } if (board[x][i] == 6) break; } return cnt; } int scanL(vector> &board, int x, int y) { int cnt = 0; for (int i = y - 1; i >= 0; i--) { if (board[x][i] == 0) { board[x][i] = 12; // mark scaned cnt++; continue; } if (board[x][i] == 6) break; } return cnt; } int scanD(vector> &board, int x, int y) { int cnt = 0; for (int i = x + 1; i < n; i++) { if (board[i][y] == 0) { board[i][y] = 13; // mark scaned cnt++; continue; } if (board[i][y] == 6) break; } return cnt; } int scanU(vector> &board, int x, int y) { int cnt = 0; for (int i = x - 1; i >= 0; i--) { if (board[i][y] == 0) { board[i][y] = 14; // mark scaned cnt++; continue; } if (board[i][y] == 6) break; } return cnt; } void func(vector> &board, int cur_cctv, int cur_scan) { if (cur_cctv == cnt_cctv) { // Investigated all cctvs cnt_scan = max(cnt_scan, cur_scan); // update cnt_scan // cout << "Board at cur_scan: " << cur_scan << "\n"; // for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // cout << board[i][j] << "\t"; // } // cout << "\n"; // } return; } auto [type, x, y] = cctv[cur_cctv]; if (type == 1) { // scan R auto copied_board_r = board; int res_scan_r = scanR(copied_board_r, x, y); func(copied_board_r, cur_cctv + 1, cur_scan + res_scan_r); // scan L auto copied_board_l = board; int res_scan_l = scanL(copied_board_l, x, y); func(copied_board_l, cur_cctv + 1, cur_scan + res_scan_l); // scan U auto copied_board_u = board; int res_scan_u = scanL(copied_board_u, x, y); func(copied_board_u, cur_cctv + 1, cur_scan + res_scan_u); // scan D auto copied_board_d = board; int res_scan_d = scanL(copied_board_d, x, y); func(copied_board_d, cur_cctv + 1, cur_scan + res_scan_d); } else if (type == 2) { // scan L&R auto copied_board_lr = board; int res_scan_lr = scanL(copied_board_lr, x, y); res_scan_lr += scanR(copied_board_lr, x, y); func(copied_board_lr, cur_cctv + 1, cur_scan + res_scan_lr); // scan U&D auto copied_board_ud = board; int res_scan_ud = scanU(copied_board_ud, x, y); res_scan_ud += scanD(copied_board_ud, x, y); func(copied_board_ud, cur_cctv + 1, cur_scan + res_scan_ud); } else if (type == 3) { // scan U&R auto copied_board_ur = board; int res_scan_ur = scanU(copied_board_ur, x, y); res_scan_ur += scanR(copied_board_ur, x, y); func(copied_board_ur, cur_cctv + 1, cur_scan + res_scan_ur); // scan R&D auto copied_board_rd = board; int res_scan_rd = scanR(copied_board_rd, x, y); res_scan_rd += scanD(copied_board_rd, x, y); func(copied_board_rd, cur_cctv + 1, cur_scan + res_scan_rd); // scan D&L auto copied_board_dl = board; int res_scan_dl = scanD(copied_board_dl, x, y); res_scan_dl += scanL(copied_board_dl, x, y); func(copied_board_dl, cur_cctv + 1, cur_scan + res_scan_dl); // scan L&U auto copied_board_lu = board; int res_scan_lu = scanL(copied_board_lu, x, y); res_scan_lu += scanU(copied_board_lu, x, y); func(copied_board_lu, cur_cctv + 1, cur_scan + res_scan_lu); } else if (type == 4) { // scan L&U&R auto copied_board_lur = board; int res_scan_lur = scanL(copied_board_lur, x, y); res_scan_lur += scanU(copied_board_lur, x, y); res_scan_lur += scanR(copied_board_lur, x, y); func(copied_board_lur, cur_cctv + 1, cur_scan + res_scan_lur); // scan U&R&D auto copied_board_urd = board; int res_scan_urd = scanU(copied_board_urd, x, y); res_scan_urd += scanR(copied_board_urd, x, y); res_scan_urd += scanD(copied_board_urd, x, y); func(copied_board_urd, cur_cctv + 1, cur_scan + res_scan_urd); // scan R&D&L auto copied_board_rdl = board; int res_scan_rdl = scanR(copied_board_rdl, x, y); res_scan_rdl += scanD(copied_board_rdl, x, y); res_scan_rdl += scanL(copied_board_rdl, x, y); func(copied_board_rdl, cur_cctv + 1, cur_scan + res_scan_rdl); // scan D&L&U auto copied_board_dlu = board; int res_scan_dlu = scanD(copied_board_dlu, x, y); res_scan_dlu += scanL(copied_board_dlu, x, y); res_scan_dlu += scanU(copied_board_dlu, x, y); func(copied_board_dlu, cur_cctv + 1, cur_scan + res_scan_dlu); } else if (type == 5) { // scan L&U&R&D auto copied_board_lurd = board; int res_scan_lurd = scanL(copied_board_lurd, x, y); res_scan_lurd += scanU(copied_board_lurd, x, y); res_scan_lurd += scanR(copied_board_lurd, x, y); res_scan_lurd += scanD(copied_board_lurd, x, y); func(copied_board_lurd, cur_cctv + 1, cur_scan + res_scan_lurd); } else { cout << "ERROR, cctv should be in range [1,5]\n"; } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; vector> board(n, vector(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> board[i][j]; } } // By scanning the given board for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // count all walls if (board[i][j] > 5) { cnt_wall++; continue; } // mark all cctvs if (board[i][j] > 0) { cctv[cnt_cctv] = {board[i][j], i, j}; cnt_cctv++; continue; } } } // backtrack all cctv (maximize scans) func(board, 0, 0); // investigating cctv-num, prefix-sum of scans cout << n * m - cnt_wall - cnt_cctv - cnt_scan; } // for (auto [type, x, y] : cctv) { // cout << "type: " << type << ", x: " << x << ", y: " << y << "\n"; // }

제출 #59336

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: