[AOJ] BOARDCOVER

[ALGOSPOT Online Judge(AOJ)] BOARDCOVER C++

๋ฌธ์ œ : AOJ BOARDCOVER

๋ฌธ์ œ ์„ค๋ช…

ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค H*W ํฌ๊ธฐ์˜ ๊ฒŒ์ž„ํŒ์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.
๊ฒŒ์ž„ํŒ์˜ ๊ฐ ์ž๋ผ๋‹ˆ๋Š” ๊ฒ€์€ ์นธ์ด๋‚˜ ํฐ ์นธ์œผ๋กœ ๋˜์–ด์žˆ๋Š”๋ฐ, L์ž ๋ชจ์–‘์˜ ๋ธ”๋ก์œผ๋กœ ํฐ ์นธ์ด ์•ˆ ๋‚จ๋„๋ก ์ฑ„์›Œ์•ผ ํ•ฉ๋‹ˆ๋‹ค.
L์ž ๋ชจ์–‘์˜ ๋ธ”๋ก์„ ์ž์œ ๋กญ๊ฒŒ ํšŒ์ „ํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, ๋ธ”๋ก๋ผ๋ฆฌ ๊ฒน์น˜๊ฑฐ๋‚˜ ๊ฒ€์€ ์นธ์„ ๋ฎ์œผ๋ฉด ์•ˆ ๋ฉ๋‹ˆ๋‹ค.
์ด๋•Œ L์ž ๋ชจ์–‘์˜ ๋ธ”๋ก์œผ๋กœ ๋ชจ๋“  ํฐ ์นธ์„ ์ฑ„์šธ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.


Solution

์™„์ „ ํƒ์ƒ‰

๊ฒŒ์ž„ํŒ์˜ ๊ฐ€์žฅ ์œ„์ชฝ, ์™ผ์ชฝ์˜ ํŒ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ์˜ค๋ฅธ์ชฝ, ์•„๋ž˜์ชฝ์œผ๋กœ ๋‚ด๋ ค๊ฐ€๋ฉฐ ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ํ•ด๊ฒฐํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
๊ฒŒ์ž„ํŒ์˜ ํ•œ ์นธ์„ ๊ธฐ์ค€ ์‚ผ์•„ ์ˆœํšŒํ•˜๋ฉด์„œ L์ž ๋ชจ์–‘์˜ ๋ธ”๋ก์ด ๊ทธ ์นธ์„ ๊ธฐ์ค€์œผ๋กœ ํšŒ์ „ํ•  ์ˆ˜ ์žˆ๋Š” ๋„ค ๊ฐ€์ง€ ๊ฒฝ์šฐ๋ฅผ ๋„ฃ์–ด์ฃผ๋ฉฐ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค.
H, W๊ฐ€ ์ตœ๋Œ€ 20์ด๋ฏ€๋กœ 400์นธ์ด ๋‚˜์˜ค๊ณ  ์ด๋ฅผ 3์œผ๋กœ ๋‚˜๋ˆ„๋ฉด ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ํฌ๊ฒŒ ๋Š๊ปด์ง€์ง€๋งŒ, ํ•˜๋‚˜์˜ L์ž ๋ธ”๋ก์„ ๋„ฃ์œผ๋ฉด ๋‹จ์ˆœํ•œ ์นธ ์ˆ˜ ๋ณด๋‹ค ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋” ์ค„์–ด๋“ค๋ฏ€๋กœ ๋” ์ ์€ ๊ฒฝ์šฐ์˜ ์ˆ˜๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


Description

  • nextMove ๋ฐฐ์—ด์„ ์ด์šฉํ•˜์—ฌ L์ž ๋ธ”๋ก์ด ํšŒ์ „ํ•  ์ˆ˜ ์žˆ๋Š” ๋„ค ๊ฐ€์ง€ ๊ฒฝ์šฐ๋ฅผ ๊ณ„์‚ฐํ–ˆ์Šต๋‹ˆ๋‹ค.
  • vector<vector<int>>& map๋กœ ๋ฐฐ์—ด์„ ํ•จ์ˆ˜์— ์ง์ ‘ ๋„ฃ์–ด์คฌ์Šต๋‹ˆ๋‹ค.
  • isOk์˜ value๊ฐ€ 1์ธ ๊ฒฝ์šฐ๋Š” L์ž ๋ธ”๋ก์„ ์ถ”๊ฐ€ํ•˜๋Š” ๊ฒฝ์šฐ, -1์ธ ๊ฒฝ์šฐ๋Š” ๋ธ”๋ก์„ ์‚ญ์ œํ•˜๋Š” ๊ฒฝ์šฐ์ž…๋‹ˆ๋‹ค.

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> map;
int nextMove[4][3][2] = { { {0,0},{1,0},{1,1} },{ {0,0},{1,0},{1,-1} },{ {0,0},{0,1},{1,1} },{ {0,0},{0,1},{1,0} } };
bool isOk(vector<vector<int>>& map, int y, int x, int type ,int value );
int chkMap(vector<vector<int>>& map);
int c, h, w;
int main(){
    cin >> c;
    while(c--){
        map.clear();
        cin >> h >> w;
        map.resize(h+1);
        for(int i=1;i<=h;i++){
            map[i].push_back(0);
            for(int j=1; j<=w;j++){
                char nowLot;
                cin >> nowLot;
                if(nowLot=='#') map[i].push_back(1);
                else map[i].push_back(0);
            }
        }
        int result = chkMap(map);
        cout << result << '\n';
    }
    return 0;
}
bool isOk(vector<vector<int>>& map, int y, int x, int type ,int value ){
    bool isOk = true;
    for(int i=0;i<3;i++){
        int ny = y + nextMove[type][i][0];
        int nx = x + nextMove[type][i][1];
        if(ny<1||nx<1||ny>h||nx>w) isOk = false;
        else if((map[ny][nx]+=value) > 1) isOk = false;
    }
    return isOk;
}
int chkMap(vector<vector<int>>& map){
    int y = -1;
    int x = -1;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(map[i][j]==0){
                y=i;
                x=j;
                break;
            }
        }
        if(y!=-1) break;
    }
    if(y ==-1) return 1;
    int ret = 0;
    for(int i=0;i<4;i++){
        if(isOk(map, y,x,i,1)) ret += chkMap(map);
        isOk(map,y,x,i,-1);
    }
    return ret;
}