QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#592894 | #833. Cells Blocking | songziyan | WA | 1550ms | 32972kb | C++14 | 2.6kb | 2024-09-27 09:38:19 | 2024-09-27 09:38:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,m,emp,cnt,ans;
int vis[N][N];
bool fs[N][N],ft[N][N];
char str[N][N];
#define pii pair<int,int>
#define fi first
#define se second
vector<pii>leftroad,rightroad;
set<pii>rightset;
bool check(pii x){return x.fi>=1&&x.se>=1&&x.fi<=n&&x.se<=m&&fs[x.fi][x.se]&&ft[x.fi][x.se];}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>str[i]+1;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)emp+=str[i][j]=='.';
fs[1][1]=str[1][1]=='.';
ft[n][m]=str[n][m]=='.';
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
if(str[i][j]!='.'||(i==1&&j==1))continue;
fs[i][j]=fs[i-1][j]|fs[i][j-1];
}
for(int i=n;i>=1;i--)for(int j=m;j>=1;j--){
if(str[i][j]!='.'||(i==n&&j==m))continue;
ft[i][j]=ft[i+1][j]|ft[i][j+1];
}
if(!fs[n][m]){
cout<<emp*(emp-1)/2<<'\n';
return 0;
}
leftroad.push_back({1,1});
rightroad.push_back({1,1});
for(int i=2;i<=n+m-1;i++){
pii a=leftroad.back();
pii b=rightroad.back();
a.fi++;if(!check(a))a.fi--,a.se++;
b.se++;if(!check(b))b.se--,b.fi++;
leftroad.push_back(a);
rightroad.push_back(b);
}
// cout<<"leftroad\n";
// for(pii i:leftroad){
// cout<<i.fi<<' '<<i.se<<'\n';
// }
// cout<<"rightroad\n";
// for(pii i:rightroad){
// cout<<i.fi<<' '<<i.se<<'\n';
// }
for(pii j:rightroad)rightset.insert(j);
for(pii i:leftroad){
if(rightset.count(i)){
vis[i.fi][i.se]=1;
++cnt;ans+=emp-cnt;
}
}
// cout<<cnt<<' '<<emp<<' '<<ans<<'\n';
for(pii i:leftroad){
if(vis[i.fi][i.se])continue;
pii x=i;
while(x==i||str[x.fi][x.se]=='#')x.fi--,x.se++;
vector<pii>up,down;
up.push_back(x);down.push_back(x);
while(up.back()!=(pii){1,1}){
pii t=up.back();
t.se--;
if(!check(t))t.fi--,t.se++;
up.push_back(t);
}
while(down.back()!=(pii){n,m}){
pii t=down.back();
t.fi++;
if(!check(t))t.fi--,t.se++;
down.push_back(t);
}
for(pii j:up){
if(vis[j.fi][j.se])continue;
if(rightset.count(j))++ans;
}
for(pii j:down){
if(j==x)continue;
if(vis[j.fi][j.se])continue;
if(rightset.count(j))++ans;
}
}
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9764kb
input:
3 3 ... ... ...
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 0
Accepted
time: 2ms
memory: 9752kb
input:
3 3 .** .*. ...
output:
15
result:
ok 1 number(s): "15"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7716kb
input:
3 4 **** .... ****
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7920kb
input:
5 5 *.... .*.*. ***** *.*** ..*..
output:
66
result:
ok 1 number(s): "66"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7716kb
input:
10 10 ...***.*.. **...*.*** ...***.*.. .**...*.*. .*****..*. ..*.****.* .**...**** ..*..*.*.* *.*.**.... ....**...*
output:
1378
result:
ok 1 number(s): "1378"
Test #6:
score: 0
Accepted
time: 1484ms
memory: 32300kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17999999
result:
ok 1 number(s): "17999999"
Test #7:
score: 0
Accepted
time: 1532ms
memory: 32972kb
input:
3000 3000 ...................................................................................................................*......................................................................................................................................................................*..........
output:
17981671
result:
ok 1 number(s): "17981671"
Test #8:
score: 0
Accepted
time: 1527ms
memory: 31404kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17963615
result:
ok 1 number(s): "17963615"
Test #9:
score: 0
Accepted
time: 1550ms
memory: 31560kb
input:
3000 3000 .........................................................................................................*...........................................................................................................................................................................................
output:
17945165
result:
ok 1 number(s): "17945165"
Test #10:
score: 0
Accepted
time: 1536ms
memory: 32536kb
input:
3000 3000 ......................................................................................................................................*........................................................................................................................................*.....................
output:
17928211
result:
ok 1 number(s): "17928211"
Test #11:
score: -100
Wrong Answer
time: 1541ms
memory: 31016kb
input:
3000 3000 ...........................................*.........................................................................................................................................................................................................................................................
output:
17911520
result:
wrong answer 1st numbers differ - expected: '17911522', found: '17911520'