ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212010 | #3815. 种树 | yangtianming001 | 100 | 8ms | 1244kb | C++11 | 1.4kb | 2024-10-13 10:07:22 | 2024-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;
}
详细
小提示:点击横条可展开更详细的信息
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