QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#600792#7733. Cool, It’s Yesterday Four Times MorewzxtslWA 2ms7924kbC++173.8kb2024-09-29 19:16:352024-09-29 19:16:36

Judging History

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

  • [2024-09-29 19:16:36]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7924kb
  • [2024-09-29 19:16:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define For(i,j,k) for (int i=(j);i<=(k);i++)
#define rof(i,j,k) for (int i=(j);i>=(k);i--)
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
#define PII pair<int,int>
#define int long long
#define endl "\n"
#define ls rt<<1
#define rs rt<<1|1
typedef long long ll;
const int mod = 998244353;
const double eps = 1e-9;
const int N=5e3+7;
int n,m;
int mi0x,mi0y,ma0x,ma0y;
struct node{
    int val;
    int mix;
    int max;
    int miy;
    int may;
}mp[N][N];
int mark1[N][N];
int mark2[N][N];
int dx[4]={0,0,-1,1};//表示要走的四个方向
int dy[4]={1,-1,0,0};
bool OK(int x,int y){
    int flag=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            flag=0;
            if(mp[i][j].val==0) continue;
            if(x==i&&y==j) continue;
            if(mp[x][y].mix>mp[i][j].mix) flag=1;
            if(mp[x][y].miy>mp[i][j].miy) flag=1;
            if(mp[x][y].max>mp[i][j].max) flag=1;
            if(mp[x][y].may>mp[i][j].may) flag=1;
            if(flag==0) return false;
        }
    }
    return true;
}
void bfs1(int x,int y){
    ma0x=max(ma0x,x),ma0y=max(ma0y,y);
    mi0x=min(mi0x,x),mi0y=min(mi0y,y);
    queue<PII> q;
    q.push({x,y});
    mark1[x][y]=0;
    while(!q.empty()){
        PII top=q.front();
        for(int i=0;i<4;i++){
            int nex=top.first+dx[i];
            int ney=top.second+dy[i];
            if(nex>=1&&nex<=n&&ney>=1&&ney<=m&&mark1[nex][ney]==-1&&mp[nex][ney].val==1){
                ma0x=max(ma0x,nex),ma0y=max(ma0y,ney);
                mi0x=min(mi0x,nex),mi0y=min(mi0y,ney);
                mark1[nex][ney]=mark1[top.first][top.second]+1;
                //cout<<mi0x<<"!"<<mi0y<<"!"<<ma0x<<"!"<<ma0y<<endl;
                q.push({nex,ney});
            }
        }
        q.pop();
    }
}
void bfs2(int x,int y){
    queue<PII> q;
    q.push({x,y});
    mark2[x][y]=0;
    mp[x][y].mix=abs(x-mi0x);
    mp[x][y].miy=abs(y-mi0y);
    mp[x][y].max=abs(ma0x-x);
    mp[x][y].may=abs(ma0y-y);
    while(!q.empty()){
        PII top=q.front();
        for(int i=0;i<4;i++){
            int nex=top.first+dx[i];
            int ney=top.second+dy[i];
            if(nex>=1&&nex<=n&&ney>=1&&ney<=m&&mark2[nex][ney]==-1&&mp[nex][ney].val==1){
                mp[nex][ney].mix=abs(nex-mi0x);
                mp[nex][ney].miy=abs(ney-mi0y);
                mp[nex][ney].max=abs(ma0x-nex);
                mp[nex][ney].may=abs(ma0y-ney);
                mark2[nex][ney]=mark2[top.first][top.second]+1;
                q.push({nex,ney});
            }
        }
        q.pop();
    }
}
void solve(){
	cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            mark1[i][j]=-1;
            mark2[i][j]=-1;
            char c;
            cin>>c;
            if(c=='.'){
                mp[i][j].val=1;
            }else{
                mp[i][j].val=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mark2[i][j]==-1&&mp[i][j].val==1){
                mi0x=0x3f3f3f3f,mi0y=0x3f3f3f3f,ma0x=0,ma0y=0;
                bfs1(i,j);
                //cout<<i<<"!"<<j<<endl;
                //cout<<mi0x<<"!"<<ma0x<<"!"<<mi0y<<"!"<<ma0y<<endl;
                bfs2(i,j);
            }else{
                continue;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j].val==1){
                if(OK(i,j)){
                    //cout<<i<<"!"<<j<<endl;
                    ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
}
signed main(){
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 2ms
memory: 7924kb

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
5
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
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:

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