QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#328536 | #833. Cells Blocking | OFforest_1273 | WA | 473ms | 79408kb | C++14 | 1.5kb | 2024-02-15 20:46:31 | 2024-02-15 20:46:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
// typedef long long ll;
int n,m;
char c[3005][3005];
bool f[3005][3005];
bool f2[3005][3005];
vector<int>v[6005];
int cnt=0,ans=0;
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1; i<=n ;i++){
for(int j=1; j<=m ;j++){
cin >> c[i][j];
f[i][j]|=f[i-1][j];
f[i][j]|=f[i][j-1];
f[i][j]|=(i==1 && j==1);
f[i][j]&=(c[i][j]=='.');
cnt+=(c[i][j]=='.');
}
}
for(int i=n;i;--i)
for(int j=m;j;--j)
f2[i][j]|=f2[i+1][j]|f2[i][j+1],f2[i][j]|=(i==n&&j==m),f2[i][j]|=(c[i][j]=='.');
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(!f[i][j]||!f2[i][j])c[i][j]='*';
else v[i+j].push_back(i);/*按对角线(右到左)分组*/
if(!f[n][m]) return cout << cnt*(cnt-1)/2 << '\n',0;
int bh=0;
for(int i=2; i<=n+m ;i++){
if(v[i].size()==1) ans+=(cnt-(++bh));
}
for(int i=2;i<=n+m;++i){
if(v[i].size()==1)continue;
int l=v[i][1],r=v[i].back();
if(l==r)++ans;
for(int j=i+1;j<=n+m;++j){
if(c[l][j-l]!='.')++l;
if(c[r+1][j-r-1]=='.')++r;
if(l==r&&v[j].size()!=1)++ans;
}
}
for(int i=2;i<=n+m;++i){
if(v[i].size()==1)continue;
int l=v[i][0],r=v[i][v[i].size()-2];
for(int j=i+1;j<=n+m;++j){
if(c[l][j-l]!='.')++l;
if(c[r+1][j-r-1]=='.')++r;
if(l==r&&v[j].size()!=1)++ans;
}
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3868kb
input:
3 3 ... ... ...
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
3 3 .** .*. ...
output:
15
result:
ok 1 number(s): "15"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
3 4 **** .... ****
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
5 5 *.... .*.*. ***** *.*** ..*..
output:
66
result:
ok 1 number(s): "66"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
10 10 ...***.*.. **...*.*** ...***.*.. .**...*.*. .*****..*. ..*.****.* .**...**** ..*..*.*.* *.*.**.... ....**...*
output:
1378
result:
ok 1 number(s): "1378"
Test #6:
score: 0
Accepted
time: 454ms
memory: 79228kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17999999
result:
ok 1 number(s): "17999999"
Test #7:
score: 0
Accepted
time: 453ms
memory: 79308kb
input:
3000 3000 ...................................................................................................................*......................................................................................................................................................................*..........
output:
17981671
result:
ok 1 number(s): "17981671"
Test #8:
score: 0
Accepted
time: 473ms
memory: 79408kb
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................
output:
17963615
result:
ok 1 number(s): "17963615"
Test #9:
score: 0
Accepted
time: 470ms
memory: 79316kb
input:
3000 3000 .........................................................................................................*...........................................................................................................................................................................................
output:
17945165
result:
ok 1 number(s): "17945165"
Test #10:
score: 0
Accepted
time: 462ms
memory: 79296kb
input:
3000 3000 ......................................................................................................................................*........................................................................................................................................*.....................
output:
17928211
result:
ok 1 number(s): "17928211"
Test #11:
score: 0
Accepted
time: 460ms
memory: 79196kb
input:
3000 3000 ...........................................*.........................................................................................................................................................................................................................................................
output:
17911522
result:
ok 1 number(s): "17911522"
Test #12:
score: 0
Accepted
time: 439ms
memory: 79016kb
input:
3000 3000 ..............................*................................................................................................................*.....................................................................................................................................................
output:
17892283
result:
ok 1 number(s): "17892283"
Test #13:
score: 0
Accepted
time: 467ms
memory: 78920kb
input:
3000 3000 ................................................................*....*................................................................................................................................................................................*..............................................
output:
17873837
result:
ok 1 number(s): "17873837"
Test #14:
score: 0
Accepted
time: 436ms
memory: 78776kb
input:
3000 3000 ............................................................................................*.............................................................................*.....................................................................................................*....................
output:
17856701
result:
ok 1 number(s): "17856701"
Test #15:
score: 0
Accepted
time: 438ms
memory: 78904kb
input:
3000 3000 ......................................*..........................................................................................................................................................*...................................................................................................
output:
17837857
result:
ok 1 number(s): "17837857"
Test #16:
score: 0
Accepted
time: 456ms
memory: 78848kb
input:
3000 3000 .................................................................................................................................................................................................................................*...................................................................
output:
17819731
result:
ok 1 number(s): "17819731"
Test #17:
score: 0
Accepted
time: 416ms
memory: 68240kb
input:
3000 3000 ......**.....*.......*.*..........*..*...............**.............*.......*......*........*...*.....*.*.................*......*....*.........*....................*.................*.......................*.......*..*.*.......*.......................*..........*..*......................*...
output:
16202000
result:
ok 1 number(s): "16202000"
Test #18:
score: -100
Wrong Answer
time: 443ms
memory: 55544kb
input:
3000 3000 ..................*....*....*...*.*.............*.............*....*.*..*...*...*...*....*.................*...*.*.***...*....*......*.......**...*.......*.*...**...*...*...**.........*..........*.....*.*....*..*.......*.........*..*.....*...............**.......*.....*.*..*.*.*........*.....
output:
21600105
result:
wrong answer 1st numbers differ - expected: '21600132', found: '21600105'