QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#328584#833. Cells BlockingHBYoutzeWA 528ms246232kbC++141.4kb2024-02-15 21:36:202024-02-15 21:36:20

Judging History

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

  • [2024-02-15 21:36:20]
  • 评测
  • 测评结果:WA
  • 用时:528ms
  • 内存:246232kb
  • [2024-02-15 21:36:20]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
//#define mod 1000000007
using namespace std;

int n,m,dp[3010][3010],dp2[3010][3010],cnt,huan,ans;
char c[3010][3010];
vector<int> ve[6010];
signed main()
{
	cin>>n>>m;
	dp[1][1]=1;dp2[n][m]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
			dp[i][j]|=dp[i-1][j];
			dp[i][j]|=dp[i][j-1];
			if(c[i][j]=='*') dp[i][j]=0;
			else cnt++;
		}
	}
	for(int i=n;i;i--)
	{
		for(int j=m;j;j--)
		{
			dp2[i][j]|=dp2[i+1][j];
			dp2[i][j]|=dp2[i][j+1];
			if(c[i][j]=='*') dp2[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(dp[i][j]&&dp2[i][j])
			{
				ve[i+j].push_back(i);huan++;
			}
			else c[i][j]='*';
		}
	}
	if(huan==0)
	{
		cout<<cnt*(cnt-1)/2;return 0;
	}
	huan=0;
	for(int i=2;i<=n+m;i++)
	{
		if(ve[i].size()==1) ans+=(cnt-(++huan));
	}
	for(int i=2;i<=n+m;i++)
	{
		if(ve[i].size()==1) continue;
		int l=ve[i][1],r=ve[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&&ve[j].size()!=1) ans++;
		}
	}
	for(int i=2;i<=n+m;i++)
	{
		if(ve[i].size()==1) continue;
		int l=ve[i][0],r=ve[i][ve[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&&ve[j].size()!=1) ans++;
		}
	}
	cout<<ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7868kb

input:

3 3
...
...
...

output:

17

result:

ok 1 number(s): "17"

Test #2:

score: 0
Accepted
time: 0ms
memory: 7828kb

input:

3 3
.**
.*.
...

output:

15

result:

ok 1 number(s): "15"

Test #3:

score: 0
Accepted
time: 0ms
memory: 7748kb

input:

3 4
****
....
****

output:

6

result:

ok 1 number(s): "6"

Test #4:

score: 0
Accepted
time: 1ms
memory: 7792kb

input:

5 5
*....
.*.*.
*****
*.***
..*..

output:

66

result:

ok 1 number(s): "66"

Test #5:

score: 0
Accepted
time: 0ms
memory: 7836kb

input:

10 10
...***.*..
**...*.***
...***.*..
.**...*.*.
.*****..*.
..*.****.*
.**...****
..*..*.*.*
*.*.**....
....**...*

output:

1378

result:

ok 1 number(s): "1378"

Test #6:

score: 0
Accepted
time: 508ms
memory: 245948kb

input:

3000 3000
.....................................................................................................................................................................................................................................................................................................

output:

17999999

result:

ok 1 number(s): "17999999"

Test #7:

score: 0
Accepted
time: 477ms
memory: 246232kb

input:

3000 3000
...................................................................................................................*......................................................................................................................................................................*..........

output:

17981671

result:

ok 1 number(s): "17981671"

Test #8:

score: 0
Accepted
time: 509ms
memory: 245968kb

input:

3000 3000
.....................................................................................................................................................................................................................................................................................................

output:

17963615

result:

ok 1 number(s): "17963615"

Test #9:

score: 0
Accepted
time: 516ms
memory: 245656kb

input:

3000 3000
.........................................................................................................*...........................................................................................................................................................................................

output:

17945165

result:

ok 1 number(s): "17945165"

Test #10:

score: 0
Accepted
time: 503ms
memory: 245564kb

input:

3000 3000
......................................................................................................................................*........................................................................................................................................*.....................

output:

17928211

result:

ok 1 number(s): "17928211"

Test #11:

score: 0
Accepted
time: 479ms
memory: 245124kb

input:

3000 3000
...........................................*.........................................................................................................................................................................................................................................................

output:

17911522

result:

ok 1 number(s): "17911522"

Test #12:

score: 0
Accepted
time: 469ms
memory: 245092kb

input:

3000 3000
..............................*................................................................................................................*.....................................................................................................................................................

output:

17892283

result:

ok 1 number(s): "17892283"

Test #13:

score: 0
Accepted
time: 502ms
memory: 244780kb

input:

3000 3000
................................................................*....*................................................................................................................................................................................*..............................................

output:

17873837

result:

ok 1 number(s): "17873837"

Test #14:

score: 0
Accepted
time: 489ms
memory: 244276kb

input:

3000 3000
............................................................................................*.............................................................................*.....................................................................................................*....................

output:

17856701

result:

ok 1 number(s): "17856701"

Test #15:

score: 0
Accepted
time: 517ms
memory: 244400kb

input:

3000 3000
......................................*..........................................................................................................................................................*...................................................................................................

output:

17837857

result:

ok 1 number(s): "17837857"

Test #16:

score: 0
Accepted
time: 507ms
memory: 243304kb

input:

3000 3000
.................................................................................................................................................................................................................................*...................................................................

output:

17819731

result:

ok 1 number(s): "17819731"

Test #17:

score: 0
Accepted
time: 500ms
memory: 215648kb

input:

3000 3000
......**.....*.......*.*..........*..*...............**.............*.......*......*........*...*.....*.*.................*......*....*.........*....................*.................*.......................*.......*..*.*.......*.......................*..........*..*......................*...

output:

16202000

result:

ok 1 number(s): "16202000"

Test #18:

score: -100
Wrong Answer
time: 528ms
memory: 185036kb

input:

3000 3000
..................*....*....*...*.*.............*.............*....*.*..*...*...*...*....*.................*...*.*.***...*....*......*.......**...*.......*.*...**...*...*...**.........*..........*.....*.*....*..*.......*.........*..*.....*...............**.......*.....*.*..*.*.*........*.....

output:

21600125

result:

wrong answer 1st numbers differ - expected: '21600132', found: '21600125'