QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#327790#833. Cells Blockingxztmax67RE 1ms3792kbC++141.2kb2024-02-15 14:21:552024-02-15 14:21:55

Judging History

你现在查看的是最新测评结果

  • [2024-02-15 14:21:55]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3792kb
  • [2024-02-15 14:21:55]
  • 提交

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
.....................................................................................................................................................................................................................................................................................................

output:


result: