QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#600792 | #7733. Cool, It’s Yesterday Four Times More | wzxtsl | WA | 2ms | 7924kb | C++17 | 3.8kb | 2024-09-29 19:16:35 | 2024-09-29 19:16:36 |
Judging History
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'