#include #define fastio ios::sync_with_stdio(0);cout.tie(0); using namespace std; int mn = 1e9; vector> v; int vsize; void resetarr(int b1[8][8], int b2[8][8]) { for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { b1[i][j] = b2[i][j]; } } } void rotate(int degree, int& n, int& m, int& x, int& y, int b[8][8]) { // n, m, x, y degree %= 4; if (degree == 0) return; int t; int b2[8][8] = {}; switch (degree) { case 1: for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { b2[i][j] = b[n - j - 1][i]; } } t = x; x = y; y = n - t - 1; t = n; n = m; m = t; break; case 2: for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { b2[i][j] = b[i][m - j - 1]; } } t = y; y = m - t - 1; break; case 3: for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { b2[i][j] = b[j][m - i - 1]; } } t = x; x = m - y - 1; y = t; t = n; n = m; m = t; break; } int k = n > m ? n : m; for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) { b[i][j] = b2[i][j]; } } } void solve(int depth, int board[8][8], int n, int m) { if (depth == vsize) { // 갱신 int c = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (board[i][j] == 0) c++; } } if (c < mn) { //for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // cout << board[i][j] << " "; // } // cout << "\n"; //} //cout << "\n"; mn = c; } return; } int b[8][8]; resetarr(b, board); int cctv = get<2>(v[depth]); int x = get<0>(v[depth]), y = get<1>(v[depth]); switch (cctv) { case 1: for (int s = 0; s < 4; s++) { rotate(s, n, m, x, y, b); for (int i = y - 1; i >= 0; i--) { if (b[x][i] == 6) break; if (b[x][i] == 0) b[x][i] = -1; } rotate(4 - s, n, m, x, y, b); solve(depth + 1, b, n, m); resetarr(b, board); } break; case 2: for (int s = 0; s < 2; s++) { rotate(s, n, m, x, y, b); for (int i = y - 1; i >= 0; i--) { if (b[x][i] == 6) break; if (b[x][i] == 0) b[x][i] = -1; } for (int i = y + 1; i < m; i++) { if (b[x][i] == 6) break; if (b[x][i] == 0) b[x][i] = -1; } rotate(4 - s, n, m, x, y, b); solve(depth + 1, b, n, m); resetarr(b, board); } break; case 3: for (int s = 0; s < 4; s++) { rotate(s, n, m, x, y, b); for (int i = y - 1; i >= 0; i--) { if (b[x][i] == 6) break; if (b[x][i] == 0) b[x][i] = -1; } for (int i = x - 1; i >= 0; i--) { if (b[i][y] == 6) break; if (b[i][y] == 0) b[i][y] = -1; } rotate(4 - s, n, m, x, y, b); solve(depth + 1, b, n, m); resetarr(b, board); } break; case 4: for (int s = 0; s < 4; s++) { rotate(s, n, m, x, y, b); for (int i = y - 1; i >= 0; i--) { if (b[x][i] == 6) break; if (b[x][i] == 0) b[x][i] = -1; } for (int i = x - 1; i >= 0; i--) { if (b[i][y] == 6) break; if (b[i][y] == 0) b[i][y] = -1; } for (int i = y + 1; i < m; i++) { if (b[x][i] == 6) break; if (b[x][i] == 0) b[x][i] = -1; } rotate(4- s, n, m, x, y, b); solve(depth + 1, b, n, m); resetarr(b, board); } break; } } int main() { fastio; int n, m; cin >> n >> m; int board[8][8]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> board[i][j]; if (board[i][j] >= 1 && board[i][j] <= 4) v.push_back({ i, j, board[i][j] }); } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (board[i][j] == 5) { for (int k = i - 1; k >= 0; k--) { if (board[k][j] == 6) break; if (board[k][j] == 0) board[k][j] = -1; } for (int k = i + 1; k < n; k++) { if (board[k][j] == 6) break; if (board[k][j] == 0) board[k][j] = -1; } for (int k = j - 1; k >= 0; k--) { if (board[i][k] == 6) break; if (board[i][k] == 0) board[i][k] = -1; } for (int k = j + 1; k < m; k++) { if (board[i][k] == 6) break; if (board[i][k] == 0) board[i][k] = -1; } } } } vsize = v.size(); solve(0, board, n, m); cout << mn; return 0; }

제출 #31418

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: