QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625263#7733. Cool, It’s Yesterday Four Times Morelibantian#WA 5ms3892kbC++234.2kb2024-10-09 18:18:252024-10-09 18:18:26

Judging History

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

  • [2024-10-09 18:18:26]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:3892kb
  • [2024-10-09 18:18:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()
int n,m;
const int N=1010;
string s[N];
bool st[N][N];
map<int,int>pl[N],pr[N],pu[N],pd[N];
int len;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
pii operator - (pii a,pii b){
    return {a.fi-b.fi,a.se-b.se};
}
void change(map<int,int>&l,map<int,int>&r,map<int,int>&up,map<int,int>&down,pii p){
    if(l.find(p.fi)==l.end())l[p.fi]=p.se;
    else l[p.fi]=min(l[p.fi],p.se);

    if(r.find(p.fi)==r.end())r[p.fi]=p.se;
    else r[p.fi]=max(r[p.fi],p.se);

    if(down.find(p.se)==down.end())down[p.se]=p.fi;
    else down[p.se]=max(down[p.se],p.fi);

    if(up.find(p.se)==up.end())up[p.se]=p.fi;
    else up[p.se]=min(up[p.se],p.fi);
}
map<int,int>getl(map<int,int>mp,pii p){
    map<int,int>res;
    for(auto v:mp){
        res[v.fi-p.fi]=v.se-p.se;
    }
    return res;
}
map<int,int>getr(map<int,int>mp,pii p){
    map<int,int>res;
    for(auto v:mp){
        res[v.fi-p.fi]=v.se-p.se;
    }
    return res;
    
}
map<int,int>getu(map<int,int>mp,pii p){
    map<int,int>res;
    for(auto v:mp){
        res[v.fi-p.se]=v.se-p.fi;
    }
    return res;
}
map<int,int>getd(map<int,int>mp,pii p){
    map<int,int>res;
    for(auto v:mp){
        res[v.fi-p.se]=v.se-p.fi;
    }
    return res;
}
void dfs(int stx,int sty){
    pii stt={stx,sty};
    vector<pii>p;
    queue<pii>q;
    q.push({stx,sty});
    p.push_back({stx,sty});
    st[stx][sty]=true;
    while(q.size()){
        auto t=q.front();
        q.pop();
        int x=t.fi,y=t.se;
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<=0||ny<=0||nx>n||ny>m||s[nx][ny]=='O'||st[nx][ny])continue;
            st[nx][ny]=true;
            q.push({nx,ny});
            p.push_back({nx,ny});
        }
    }
    map<int,int>posl,posr,posu,posd;
    for(auto point:p){
        auto t=point-stt;
        //cout<<t.fi<<" "<<t.se<<endl;
        change(posl,posr,posu,posd,point-stt);
    }
    // cout<<endl;
    //  for(auto v:posl){
    //         cout<<v.fi<<" "<<v.se;
    //     }
    //     cout<<endl;
    //     for(auto v:posr){
    //         cout<<v.fi<<" "<<v.se;
    //     }
    //     cout<<endl;
    //     for(auto v:posu){
    //         cout<<v.fi<<" "<<v.se;
    //     }
    //     cout<<endl;
    //     for(auto v:posd){
    //         cout<<v.fi<<" "<<v.se;
    //     }
    //     cout<<endl;
    //     cout<<"======="<<endl;
    for(auto point:p){
        //cout<<point.fi<<" "<<point.se<<endl;
        pl[++len]=getl(posl,point-stt);
        pr[len]=getr(posr,point-stt);
        pu[len]=getu(posu,point-stt);
        pd[len]=getd(posd,point-stt);
    }
    
}
bool checklr(int a,int b){
    for(auto v:pl[a]){
        if(pl[b].find(v.fi)==pl[b].end())return false;
        if(pl[b][v.fi]<=pl[a][v.fi]&&pr[a][v.fi]<=pr[b][v.fi]){

        }else return false;

    }
    return true;
}
bool checkud(int a,int b){
    for(auto v:pu[a]){
        if(pu[b].find(v.fi)==pu[b].end())return false;
        if(pu[b][v.fi]<=pu[a][v.fi]&&pd[a][v.fi]<=pd[b][v.fi]){

        }else return false;

    }
    return true;
}
void solve(){
    cin>>n>>m;
    len=0;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
        for(int j=1;j<=m;j++)st[i][j]=false;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!st[i][j]&&s[i][j]=='.')dfs(i,j);
        }
    }
    int res=0;
    for(int i=1;i<=len;i++){
        bool is=true;
        for(int j=1;j<=len;j++){
            if(j==i)continue;
            if(n<m){
                if(checklr(i,j)){
                    is=false;
                }
            }else{
                if(checkud(i,j)){
                    is=false;
                }
            }
        }
        if(is)res++;
    }
    cout<<res<<endl;
    
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << setiosflags(ios::fixed) << setprecision(15);
    int T;
    T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3792kb

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: 0
Accepted
time: 2ms
memory: 3804kb

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
7
9
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
7
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
3
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
6
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
1...

result:

ok 200 lines

Test #3:

score: -100
Wrong Answer
time: 5ms
memory: 3892kb

input:

50
10 9
OOOO.O...
O...O.OOO
.....O...
..OO..O.O
...O..O.O
..OOO..O.
..OOO...O
.OO.O..OO
.O.O.OO..
.O..O.O.O
10 10
.O.OOO.OO.
...OOOOOOO
...O.O..O.
.O.O..O...
.O.O.OO..O
..OO.O..OO
O....O..OO
OO...OOOOO
OO.OO.O..O
.O.O.OOOOO
10 8
O..OOO.O
O.OOOO..
O..OO.OO
OO..OO..
.OOO..O.
.OO.OO.O
OOO..OO.
..O..OO....

output:

31
40
8
25
40
37
16
29
20
26
25
29
14
29
21
23
24
31
25
34
25
22
12
14
41
28
16
31
20
29
18
21
21
28
35
13
20
17
32
29
28
23
15
23
14
18
28
17
35
24

result:

wrong answer 3rd lines differ - expected: '13', found: '8'