UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212010#3815. 种树yangtianming0011008ms1244kbC++111.4kb2024-10-13 10:07:222024-10-13 12:54:45

answer

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <algorithm>
using namespace std;
bool f(const vector<pair<int, int>>& p, int n, int m) {
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    set<pair<int, int>> ps(p.begin(), p.end());

    for (const auto& pos : p) {
        int x = pos.first, y = pos.second;
        for (const auto& dir : directions) {
            int nx = x + dir.first;
            int ny = y + dir.second;
            if (ps.count({nx, ny})) {
                return false;  
            }
        }
    }
    return true;  
}


int main() {
    int n, m, k;
    cin >> n >> m >> k;
    if (k == 0) {
        return 1; 
    }
    vector<pair<int, int>> cells;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cells.emplace_back(i, j);
        }
    }

    int valid_count = 0;
    vector<bool> select(cells.size(), false);
    fill(select.begin(), select.begin() + k, true);  

    do {
        vector<pair<int, int>> a;
        for (int i = 0; i < cells.size(); ++i) {
            if (select[i]) {
                a.push_back(cells[i]);
            }
        }
        if (f(a, n, m)) {
            valid_count++;
        }
    } while (prev_permutation(select.begin(), select.end()));
    cout << valid_count<< endl;

    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1240kb

input:

2 2 1

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

2 3 2

output:

8

result:

ok 1 number(s): "8"

Test #3:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

4 4 2

output:

96

result:

ok 1 number(s): "96"

Test #4:

score: 10
Accepted
time: 6ms
memory: 1244kb

input:

4 4 5

output:

304

result:

ok 1 number(s): "304"

Test #5:

score: 10
Accepted
time: 0ms
memory: 1240kb

input:

3 4 3

output:

84

result:

ok 1 number(s): "84"

Test #6:

score: 10
Accepted
time: 0ms
memory: 1240kb

input:

3 5 2

output:

83

result:

ok 1 number(s): "83"

Test #7:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

3 5 3

output:

215

result:

ok 1 number(s): "215"

Test #8:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

3 5 4

output:

276

result:

ok 1 number(s): "276"

Test #9:

score: 10
Accepted
time: 2ms
memory: 1244kb

input:

3 5 5

output:

174

result:

ok 1 number(s): "174"

Test #10:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

4 3 5

output:

18

result:

ok 1 number(s): "18"

Extra Test:

score: 0
Extra Test Passed