QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561319#7733. Cool, It’s Yesterday Four Times MorelihuaijiaoWA 1ms5700kbC++202.7kb2024-09-12 21:47:052024-09-12 21:47:07

Judging History

你现在查看的是最新测评结果

  • [2024-09-12 21:47:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5700kb
  • [2024-09-12 21:47:05]
  • 提交

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'