QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#601491 | #7733. Cool, It’s Yesterday Four Times More | kans2298 | WA | 0ms | 3512kb | C++20 | 3.6kb | 2024-09-30 01:43:33 | 2024-09-30 01:43:33 |
Judging History
answer
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include<set>
#define encode(x,y) (x*(m+1)+y)
using namespace std;
const int way[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
int main()
{
int t, ti;
//freopen("input.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
for (ti = 1; ti <= t; ++ti)
{
int n, m, i, j, cnt1 = 0;
cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int>(m + 1));
vector<vector<int>> b(n + 1, vector<int>(m + 1,-1));
for (i = 1; i <= n; ++i)
{
string s;
cin >> s;
for (j = 0; j < m; ++j)
if (s[j] == '.')
a[i][j + 1] = 1; // 1 means empty area
else
a[i][j + 1] = 0; // 0 means unexisted way
}
vector<vector<pair<int, int>>> all_block;
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
if (a[i][j] == 1 && b[i][j] == -1)
{
auto bfs = [&]()
{
queue<pair<int, int>> q;
vector<pair<int, int>> new_block;
q.push({i, j});
b[i][j] = cnt1;
new_block.push_back({i, j});
while (q.empty() == false)
{
const auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; ++k)
{
const int nx = x + way[k][0], ny = y + way[k][1];
if (not (nx>=1 && nx<=n && ny>=1 && ny<=m)) continue;
if (a[nx][ny] == 1 && b[nx][ny] == -1)
{
q.push({nx, ny});
b[nx][ny] = cnt1;
new_block.push_back({nx, ny});
}
}
}
all_block.push_back(new_block);
};
bfs();
++cnt1;
}
vector<set<int> > c;
for (i=1;i<=n;++i)
for (j=1;j<=m;++j)
if (a[i][j]==1)
{
int idx=b[i][j];
set<int> s;
for (auto [x,y]:all_block[idx])
s.insert(encode(x-i,y-j));
c.push_back(s);
}
int ans=0;
for (i=0;i<c.size();++i)
{
int oppo=c.size()-1;
for (j=0;j<c.size();++j)
{
if (i==j) continue;
for (const auto point:c[i])
if (c[j].count(point)==0)
{
oppo-=1;
break;
}
}
if (oppo==0) ++ans;
}
cout<<ans<<"\n";
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3512kb
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO
output:
4 1 0 0
result:
wrong answer 1st lines differ - expected: '3', found: '4'