QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#561209	#7733. Cool, It’s Yesterday Four Times More	lihuaijiao	WA	2ms	7752kb	C++17	2.7kb	2024-09-12 21:13:47	2024-09-12 21:13:52

Judging History

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

[2024-09-12 21:13:52]
评测

测评结果：WA
用时：2ms
内存：7752kb

查看

[2024-09-12 21:13:47]
提交

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[5] = {0, 1, -1, 0, 0};
ll zy[5] = {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 i, ll j){
    for(auto x: tu[j]){
        ll flg = 0;
        for(auto y: tu[i]){
            ll newx = x.first + y.first;
            ll newy = x.second + y.second;
            if(tu[j].find(make_pair(newx, newy)) == tu[j].end()){
                flg = 1;
                break;
            }
        }
        if(!flg) return 1; 
    }
    return 0;
}
int main(){
    ll t;
    cin >> t;
    while (t--){
        ll f = 0;
        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可以包含j
                }
            }
        }
        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 && tu[i].size() > tu[j].size()){
                    continue;
                }
                flg = 1;
            }
            if(!flg){
                cout << tu[i].size() << endl;
                f = 1;
                break;
            }
        }
        if(!f) cout << 0 << 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;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 5756kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

result:

ok 4 lines

Test #2:

score: -100

Wrong Answer

time: 2ms

memory: 7752kb

input:

200
2 4
OOO.
OO..
2 3
OOO
.O.
3 3
O.O
OOO
OO.
4 1
.
.
O
O
1 2
.O
1 1
.
2 5
.OO..
.O.O.
2 1
O
O
1 1
O
1 3
.OO
5 1
O
O
.
O
.
5 2
O.
..
O.
.O
..
5 3
...
...
.OO
..O
OOO
3 5
..O.O
.O.O.
.OO.O
5 2
.O
OO
O.
O.
..
2 1
O
O
3 5
.O.OO
O...O
..OO.
1 5
.....
5 1
O
.
O
.
.
5 3
OOO
OO.
.OO
OO.
O.O
2 1
O
.
5 2
O.
...

output:

result:

wrong answer 12th lines differ - expected: '7', found: '0'