QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#592974 | #833. Cells Blocking | songziyan | WA | 2209ms | 32496kb | C++14 | 2.8kb | 2024-09-27 10:42:06 | 2024-09-27 10:42:06 |
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;
// cout<<i.fi<<','<<i.se<<":\n";
pii x=i;
while(x==i||str[x.fi][x.se]=='#'||!check(x))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);
}
// reverse(up.begin(),up.end());
// int sum=0;
for(pii j:up){
// cout<<j.fi<<' '<<j.se<<'\n';
if(vis[j.fi][j.se])continue;
if(rightset.count(j))++ans;
}
for(pii j:down){
if(j==x)continue;
// cout<<j.fi<<' '<<j.se<<'\n';
if(vis[j.fi][j.se])continue;
if(rightset.count(j))++ans;
}
// cout<<sum<<'\n';
}
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9696kb
input:
3 3 ... ... ...
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9760kb
input:
3 3 .** .*. ...
output:
15
result:
ok 1 number(s): "15"
Test #3:
score: 0
Accepted
time: 0ms
memory: 7720kb
input:
3 4 **** .... ****
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7928kb
input:
5 5 *.... .*.*. ***** *.*** ..*..
output:
66
result:
ok 1 number(s): "66"
Test #5:
score: 0
Accepted
time: 1ms
memory: 7672kb
input:
10 10 ...***.*.. **...*.*** ...***.*.. .**...*.*. .*****..*. ..*.****.* .**...**** ..*..*.*.* *.*.**.... ....**...*
output:
1378
result:
ok 1 number(s): "1378"
Test #6:
score: 0
Accepted
time: 1551ms
memory: 32200kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17999999
result:
ok 1 number(s): "17999999"
Test #7:
score: 0
Accepted
time: 1596ms
memory: 32004kb
input:
3000 3000 ...................................................................................................................*......................................................................................................................................................................*..........
output:
17981671
result:
ok 1 number(s): "17981671"
Test #8:
score: 0
Accepted
time: 1573ms
memory: 31924kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17963615
result:
ok 1 number(s): "17963615"
Test #9:
score: 0
Accepted
time: 1582ms
memory: 31544kb
input:
3000 3000 .........................................................................................................*...........................................................................................................................................................................................
output:
17945165
result:
ok 1 number(s): "17945165"
Test #10:
score: 0
Accepted
time: 1583ms
memory: 31260kb
input:
3000 3000 ......................................................................................................................................*........................................................................................................................................*.....................
output:
17928211
result:
ok 1 number(s): "17928211"
Test #11:
score: 0
Accepted
time: 1550ms
memory: 30892kb
input:
3000 3000 ...........................................*.........................................................................................................................................................................................................................................................
output:
17911522
result:
ok 1 number(s): "17911522"
Test #12:
score: 0
Accepted
time: 1608ms
memory: 32236kb
input:
3000 3000 ..............................*................................................................................................................*.....................................................................................................................................................
output:
17892283
result:
ok 1 number(s): "17892283"
Test #13:
score: 0
Accepted
time: 1603ms
memory: 30704kb
input:
3000 3000 ................................................................*....*................................................................................................................................................................................*..............................................
output:
17873837
result:
ok 1 number(s): "17873837"
Test #14:
score: 0
Accepted
time: 1589ms
memory: 31784kb
input:
3000 3000 ............................................................................................*.............................................................................*.....................................................................................................*....................
output:
17856701
result:
ok 1 number(s): "17856701"
Test #15:
score: 0
Accepted
time: 1588ms
memory: 30528kb
input:
3000 3000 ......................................*..........................................................................................................................................................*...................................................................................................
output:
17837857
result:
ok 1 number(s): "17837857"
Test #16:
score: 0
Accepted
time: 1565ms
memory: 30712kb
input:
3000 3000 .................................................................................................................................................................................................................................*...................................................................
output:
17819731
result:
ok 1 number(s): "17819731"
Test #17:
score: 0
Accepted
time: 1886ms
memory: 31716kb
input:
3000 3000 ......**.....*.......*.*..........*..*...............**.............*.......*......*........*...*.....*.*.................*......*....*.........*....................*.................*.......................*.......*..*.*.......*.......................*..........*..*......................*...
output:
16202000
result:
ok 1 number(s): "16202000"
Test #18:
score: 0
Accepted
time: 2209ms
memory: 32496kb
input:
3000 3000 ..................*....*....*...*.*.............*.............*....*.*..*...*...*...*....*.................*...*.*.***...*....*......*.......**...*.......*.*...**...*...*...**.........*..........*.....*.*....*..*.......*.........*..*.....*...............**.......*.....*.*..*.*.*........*.....
output:
21600132
result:
ok 1 number(s): "21600132"
Test #19:
score: -100
Wrong Answer
time: 55ms
memory: 30040kb
input:
3000 3000 ..*.**...*...............*........*.*..*.*.....*........*.*..........***..*..*..*..*.*....*...*.*.....***.*...*........*..*.****..*.*....**.......*......*....*..*......*......*..*..*.*..*....*..**.*.......**.*...*....**.....**..*......*...*....*..*.**.*..***...*.....*....***.*........*.......
output:
703170079
result:
wrong answer 1st numbers differ - expected: '19862779430431', found: '703170079'