QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561319 | #7733. Cool, It’s Yesterday Four Times More | lihuaijiao | WA | 1ms | 5700kb | C++20 | 2.7kb | 2024-09-12 21:47:05 | 2024-09-12 21:47:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const ll N = 1e3 + 10;
char a[N][N];
ll vis[N][N];
set<PII> tu[N];
ll tot;
ll zx[10] = {0, 1, -1, 0, 0};
ll zy[10] = {0, 0, 0, 1, -1};
ll xx, yy;
ll n, m;
void dfs(ll x, ll y){
tu[tot].insert(make_pair(x - xx, y - yy));
vis[x][y] = 1;
for(ll i = 1; i <= 4; i++){
ll tx = x + zx[i];
ll ty = y + zy[i];
if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
if(!vis[tx][ty] && a[tx][ty] == '.'){
dfs(tx, ty);
}
}
}
ll bh[N][N];
ll pd(ll ti, ll tj){
for(auto x: tu[tj]){
ll flg = 0;
for(auto y: tu[ti]){
ll newx = x.first + y.first;
ll newy = x.second + y.second;
if(tu[tj].find(make_pair(newx, newy)) == tu[tj].end()){
flg = 1;
break;
}
}
if(!flg) return 0;
}
return 1;
}
int main(){
ll t;
cin >> t;
while (t--){
cin >> n >> m;
// cout << tu[1].size() << endl;
for (ll i = 1; i <= n; i++){
for (ll j = 1; j <= m; j++){
cin >> a[i][j];
}
}
tot = 0;
for (ll i = 1; i <= n; i++){
for (ll j = 1; j <= m; j++){
if (!vis[i][j] && a[i][j] == '.'){
tot++;
xx = i;
yy = j;
dfs(i, j);
}
}
}
for(ll i = 1; i <= tot; i++){
for(ll j = 1; j <= tot; j++){
if(i == j) continue;
if(pd(j, i)){
bh[i][j] = 1; //i可以kill j
}
}
}
ll ans = 0;
for(ll i = 1; i <= tot; i++){
ll flg = 0;
for(ll j = 1; j <= tot; j++){
if(i == j) continue;
if(bh[i][j] == 1){
continue;
}
flg = 1;
}
if(!flg){
ans += tu[i].size();
}
}
cout << ans << endl;
for(ll i = 1; i <= tot; i++){
// cout << "cao" << endl;
tu[i].clear();
// cout << tu[i].size() << endl;
}
for(ll i = 1; i <= tot; i++){
for(ll j = 1; j <= tot; j++){
bh[i][j] = 0;
}
}
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= m; j++){
vis[i][j] = 0;
}
}
// cout << "?" << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5700kb
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO
output:
1 1 0 0
result:
wrong answer 1st lines differ - expected: '3', found: '1'