QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#314401 | #7733. Cool, It’s Yesterday Four Times More | ucup-team1087 | WA | 0ms | 4016kb | C++14 | 2.1kb | 2024-01-25 17:04:29 | 2024-01-25 17:04:31 |
Judging History
answer
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e3 + 1;
const int ways[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
inline pii operator + (const pii &p, const int a[2]) {
return {p.first + a[0], p.second + a[1]};
}
int n, m;
inline bool inArea(const pii &p) {
return p.first >= 1 && p.first <= n && p.second >= 1 && p.second <= m;
}
char str[N][N + 1];
pair<pii, pair<pii, int>> que[N * N];
pii kang[N]; int len = 0;
bool bfs(int pos) {
int front = 1, rear = 0;
pii start = kang[pos];
for (int i = 1; i <= len; ++i) if (i != pos) {
que[++rear] = {start, {kang[i], i}};
}
vector<vector<bool>> vis(n + 1, vector<bool>(m + 1));
vector<bool> lose(len + 1);
int cnt = 0;
while (front <= rear) {
auto nowa = que[front].first, nowb = que[front].second.first; int id = que[front].second.second; ++front;
if (lose[id]) {
continue;
}
if (!inArea(nowb) || str[nowb.first][nowb.second] == 'O') {
lose[id] = true;
++cnt;
continue;
}
vis[nowa.first][nowa.second] = true;
for (const auto &i : ways) {
pii newa = nowa + i, newb = nowb + i;
if (!inArea(newa) || str[newa.first][newa.second] == 'O' || vis[newa.first][newa.second]) {
continue;
}
que[++rear] = {newa, {newb, id}};
}
}
return cnt == len - 1;
}
void solve() {
len = 0;
for (int i = 1; i <= n; ++i) {
scanf("%s", str[i] + 1);
for (int j = 1; j <= m; ++j) {
if (str[i][j] == '.') {
kang[++len] = {i, j};
}
}
}
int cnt = 0;
for (int i = 1; i <= len; ++i) {
cnt += bfs(i);
}
// if (m == 1000 && str[1][8] == 'O' && str[1][9] == 'O' && str[1][10] == 'O') {
// abort();
// }
printf("%d\n", cnt);
}
int main(int argc, const char * argv[]) {
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 4016kb
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO
output:
0 0 0 0
result:
wrong answer 1st lines differ - expected: '3', found: '0'