QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#328260 | #833. Cells Blocking | wYYSZL | WA | 1ms | 4228kb | C++14 | 1.6kb | 2024-02-15 18:44:25 | 2024-02-15 18:44:27 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
char a[3005][3005];
bool f[3005][3005];
bool g[3006][3005];
int ans;
vector<int>xl[6005];
int num;
signed main(){
cin.tie(0)->sync_with_stdio(0);
freopen("1.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
cin>>a[i][j];
num+=(a[i][j]=='.');
}
if(a[1][1]=='*'){cout<<num*(num-1)/2<<'\n';return 0;}
f[1][1]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
if(a[i][j]=='*')continue;
if(i==j and i==1)continue;
f[i][j]=(f[i-1][j] or f[i][j-1]);
}
if(!f[n][m]){cout<<num*(num-1)/2<<'\n';return 0;}
cerr<<'a';
g[n][m]=1;
for(int i=n;i;--i)
for(int j=m;j;--j){
if(g[i][j]=='*')continue;
if(i==n and j==m)continue;
g[i][j]=(g[i+1][j] or g[i][j+1]);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
if(f[i][j] and g[i][j])
xl[i+j].push_back(i);
}
int tp=0;
for(int i=1;i<=n+m;++i){
if(xl[i].size()==1)
ans+=num-1-(tp++);
}
for(int i=2;i<=n+m;++i){
if(xl[i].size()==1)continue;
int x1=xl[i][1],x2=*(--xl[i].end());
if(x1==x2)++ans;
for(int j=i+1;j<=n+m;++j){
if(!f[x1][j-x1] or !g[x1][j-x1])++x1;
if(f[x2+1][j-x2-1] and g[x2+1][j-x2-1])++x2;
if(x1==x2 and xl[j].size()!=1)++ans;
}
}
for(int i=2;i<=n+m;++i){
if(xl[i].size()==1)continue;
int x1=xl[i][0],x2=*(--(--xl[i].end()));
for(int j=i+1;j<=n+m;++j){
if(!f[x1][j-x1] or !g[x1][j-x1])++x1;
if(f[x2+1][j-x2-1] and g[x2+1][j-x2-1])++x2;
if(x1==x2 and xl[j].size()!=1)++ans;
}
}
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4228kb
input:
3 3 ... ... ...
output:
0
result:
wrong answer 1st numbers differ - expected: '17', found: '0'