jongmanbook/jongman_1_9.4_answer.cpp at main · jakdurider/jongmanbook · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <string>
using namespace std;

int total;
const int cen_dx[4] = {-1,-1,1,1};
const int cen_dy[4] = {-1,1,-1,1};
const int side_dx[8] = {-1,1,-1,1,-1,1,-1,1};
const int side_dy[8] = {1,1,-1,-1,-1,-1,1,1};
void solve(bool** covered, int h, int w){
    int x = -1;
    int y = -1;

    for(int i=0;i<h;++i){
        for(int j=0;j<w;++j){
            if(!covered[i][j]){
                x = j; y = i; break;
            }
        }
        if(x!=-1) break;
    }

    if(x==-1) ++total;
    else{
        for(int i=0;i<4;++i){
            int another_x = x+cen_dx[i];
            int another_y = y+cen_dy[i];
            if(another_x>=0 && another_x < w && another_y>=0 && another_y < h && !covered[another_y][x] && !covered[y][another_x]){

                covered[y][x] = true;
                covered[another_y][x] = true;
                covered[y][another_x] = true;
                solve(covered,h,w);
                covered[y][x] = false;
                covered[another_y][x] = false;
                covered[y][another_x] = false;

            }
        }
        for(int i=0;i<8;++i){
            int another_x = x+side_dx[i];
            int another_y = y+side_dy[i];
            if(i<4){
                if(another_x>=0 && another_x < w && another_y>=0 && another_y < h && !covered[another_y][another_x] && !covered[another_y][x]){

                    covered[y][x] = true;
                    covered[another_y][another_x] = true;
                    covered[another_y][x] = true;
                    solve(covered,h,w);
                    covered[y][x] = false;
                    covered[another_y][another_x] = false;
                    covered[another_y][x] = false;

                }
            }
            else{
                if(another_x>=0 && another_x < w && another_y>=0 && another_y < h && !covered[another_y][another_x] && !covered[y][another_x]){

                    covered[y][x] = true;
                    covered[another_y][another_x] = true;
                    covered[y][another_x] = true;
                    solve(covered,h,w);
                    covered[y][x] = false;
                    covered[another_y][another_x] = false;
                    covered[y][another_x] = false;

                }
            }

        }
    }
}

int main()
{
    int C;
    cin >> C;
    for(int test=0;test<C;++test){
        total = 0;
        int h,w;
        cin >> h >> w;
        bool ** covered = new bool* [h];
        for(int i=0;i<h;++i){
            covered[i] = new bool[w];
        }
        for(int i=0;i<h;++i){
            for(int j=0;j<w;++j){
                covered[i][j] = false;
            }
        }
        for(int i=0;i<h;++i){
            string str;
            cin >> str;
            for(int j=0;j<w;++j){
                if(str[j] == '#') covered[i][j] = true;
            }
        }
        solve(covered,h,w);
        cout << total << endl;
        for(int i=0;i<h;++i){
            delete[] covered[i];
        }
        delete[] covered;
    }

    return 0;
}