-
algospot - boardcoverAlgorithm/알고스팟 2020. 1. 17. 02:3312345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394//algospot - boardcover#include <iostream>#include <vector>using namespace std;int H, W;int ans;vector<vector<bool>> board;int xa1[4] = {1, 1, 0, 0};int ya1[4] = {-1, 0, 1, 1};int xa2[4] = {1, 1, 1, 1};int ya2[4] = {0, 1, 0, 1};void bf(int x, int y);void init(){ans = 0;cin >> H >> W;board = vector<vector<bool>>(H, vector<bool>(W));char c;for (int i = 0; i < H; i++)for (int j = 0; j < W; j++){cin >> c;if (c == '#')board[i][j] = false;else if(c == '.')board[i][j] = true;}}void next(int x, int y){if (y == W - 1)bf(x + 1, 0);elsebf(x, y + 1);}bool check(int x, int y, int cse, bool cover){if(cover){if(x+xa1[cse] < 0 || x+xa1[cse] >= H || x+xa2[cse] < 0 || x+xa2[cse] >= H|| y+ya1[cse] < 0 || y+ya1[cse] >= W || y+ya1[cse] < 0 || y+ya1[cse] >= W)return false;if(board[x+xa1[cse]][y+ya1[cse]] && board[x+xa2[cse]][y+ya2[cse]]){board[x+xa1[cse]][y+ya1[cse]] = board[x+xa2[cse]][y+ya2[cse]] = false;return true;}return false;}elseboard[x+xa1[cse]][y+ya1[cse]] = board[x+xa2[cse]][y+ya2[cse]] = true;}void bf(int x, int y){if(x == H){++ans;return;}else if (!board[x][y]){next(x, y);return;}bool flag;for (int i = 0; i < 4; ++i){flag = check(x, y, i, true);if (flag){next(x, y);check(x, y, i, false);}}}int main(){int C;cin >> C;for (int t_num = 0; t_num < C; ++t_num){init();bf(0, 0);cout << ans << "\n";}}
cs https://algospot.com/judge/problem/read/BOARDCOVER
algospot.com :: BOARDCOVER
게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다. 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요. 입력 력의 첫
algospot.com
Boardcover
전형적인 브루트포스 문제
'Algorithm > 알고스팟' 카테고리의 다른 글
algospot - hanoi4 (0) 2020.01.17 algospot - picnic (0) 2020.01.17 algospot - routing (0) 2020.01.15 algospot - sortgame (0) 2020.01.10 algospot - wordchain (0) 2020.01.10