QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#327790 | #833. Cells Blocking | xztmax67 | RE | 1ms | 3792kb | C++14 | 1.2kb | 2024-02-15 14:21:55 | 2024-02-15 14:21:55 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e3+100;
int n,m,cnt,ans;
char c[N][N];
int dp[N][N],dp2[N][N];
vector<int>vt[N];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>c[i][j],cnt+=c[i][j]=='.';
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
dp[i][j]|=dp[i-1][j]|dp[i][j-1]|(i==1&&j==1),
dp[i][j]&=c[i][j]=='.';
for(int i=n; i>=1 ;i--)for(int j=m; j>=1 ;j--)
dp2[i][j]|=dp2[i+1][j]|dp2[i][j+1]|(i==n&&j==m),
dp2[i][j]&=c[i][j]=='.';
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!dp[i][j]||!dp2[i][j]) c[i][j]='*';
else vt[i+j].push_back(i);
if(!dp[n][m])return cout<<cnt*(cnt-1)/2<<endl,0;
int tmp=0;for(int i=2;i<=n+m;i++)if(vt[i].size()==1)ans+=(cnt-(++tmp));
for(int i=2; i<=n+m ;i++)
{
if(vt[i].size()==1) continue;
int l=vt[i][1],r=vt[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&&vt[j].size()!=1) ans++;
}
l=vt[i][0],r=vt[i][vt[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&&vt[j].size()!=1)ans++;
}
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3740kb
input:
3 3 ... ... ...
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
3 3 .** .*. ...
output:
15
result:
ok 1 number(s): "15"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
3 4 **** .... ****
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3692kb
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: -100
Runtime Error
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................