QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722344#7733. Cool, It’s Yesterday Four Times Moreparamec1um#WA 0ms5876kbC++202.6kb2024-11-07 18:40:582024-11-07 18:40:59

Judging History

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

  • [2024-11-07 18:40:59]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5876kb
  • [2024-11-07 18:40:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int mp[N][N], vis[N][N];
struct Node{
    int cnt;
    int l, r, u ,d;
}a[N];
int cnt;
int n, m;
int dx[4]={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0};
void dfs(int x, int y, int id){
    ++a[id].cnt;
    vis[x][y]=1;
    if(x<a[id].u) a[id].u=x;
    if(x>a[id].d) a[id].d=x;
    if(y<a[id].l) a[id].l=y;
    if(y>a[id].r) a[id].r=y;
    for(int i=0; i<4; ++i){
        int tx=x+dx[i], ty=y+dy[i];
        if(tx>=1 && tx<=n && ty>=1 && ty<=m && !vis[tx][ty] && mp[tx][ty]) dfs(tx, ty, id);
    }
}
inline void solve(){
    cnt=0;
    
    cin>>n>>m;
    for(int i=1; i<=n; ++i){
        memset(mp[i]+1, 0, m*sizeof(int));
        memset(vis[i]+1, 0, m*sizeof(int));
    }
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            char c;
            cin>>c;
            if(c=='.'){
                mp[i][j]=1;
            }
        }
    }
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j){
            if(mp[i][j] && !vis[i][j]){
                ++cnt;
                a[cnt].cnt=0;
                a[cnt].l=j, a[cnt].r=j;
                a[cnt].u=i, a[cnt].d=i;
                dfs(i, j, cnt);
            }
        }
    }
    // for(int i=1; i<=cnt; ++i){
    //     cout<<"i: "<<i<<" "<<a[i].cnt<<"\n";
    //     cout<<a[i].l<<" "<<a[i].r<<" "<<a[i].u<<" "<<a[i].d<<"\n";
    // }
    vector<int> id1(cnt), id2(cnt);
    for(int i=0; i<cnt; ++i) id1[i]=i+1, id2[i]=i+1;
    sort(id1.begin(), id1.end(), [&](const int& A, const int& B){
        int wA=a[A].r-a[A].l+1, wB=a[B].r-a[B].l+1;
        int hA=a[A].d-a[A].u+1, hB=a[B].d-a[B].u+1;
        return wA==wB ? hA>hB : wA>wB;
    });
    sort(id2.begin(), id2.end(), [&](const int& A, const int& B){
        int wA=a[A].r-a[A].l+1, wB=a[B].r-a[B].l+1;
        int hA=a[A].d-a[A].u+1, hB=a[B].d-a[B].u+1;
        return hA==hB ? wA>wB : hA>hB;
    });
    // for(auto&& i: id1) cout<<i<<" ";
    // cout<<"\n";
    // for(auto&& i: id2) cout<<i<<" ";
    // cout<<"\n";
    if(cnt==0){
        cout<<0<<"\n";
    }else if(cnt==1){
        cout<<a[cnt].cnt<<"\n";
    }else{
        int ans=0;
        int flagw=1, flagh=1;
        if((a[id1[0]].r-a[id1[0]].l)!=(a[id1[1]].r-a[id1[1]].l)) ans+=a[id1[0]].cnt;
        else flagw=0;
        if((a[id2[0]].d-a[id2[0]].u)!=(a[id2[1]].d-a[id2[1]].u)) ans+=a[id2[0]].cnt;
        else flagh=0;
        if(id1[0]==id2[0] && flagw && flagh) ans-=a[id1[0]].cnt;
        cout<<ans<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5876kb

input:

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

output:

3
1
0
0

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 5600kb

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:

3
0
0
2
1
1
3
0
0
1
0
4
9
4
4
0
6
5
2
0
1
6
4
0
2
0
0
5
3
3
1
4
1
0
4
5
2
3
7
3
0
6
2
2
2
0
4
6
6
3
3
2
3
5
2
1
0
3
3
4
4
2
2
0
7
6
4
8
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
6
1
6
2
2
0
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
6
2
5
1
3
3
4
0
2
11
2
2
4
0
4
4
3
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
1...

result:

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