QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#328338#833. Cells Blockinghy233TL 1ms3912kbC++141.6kb2024-02-15 19:18:442024-02-15 19:18:45

Judging History

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

  • [2024-02-15 19:18:45]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3912kb
  • [2024-02-15 19:18:44]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3005;
const int inf=1e9;
inline int rd()
{
	int x=0; bool f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-') f=0;
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=x*10+(ch^48);
	return f?x:-x;
}
int n,m;
char s[N][N];
bool gd[N][N];
int col[N][N];
void dfs(int x,int y)
{
	if(x>n||y>m) return;
	if(s[x][y]=='*') return;
	dfs(x+1,y);
	dfs(x,y+1);
	if(gd[x+1][y]||gd[x][y+1])
		gd[x][y]=1;
}
int main()
{
	n=rd(),m=rd();
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	gd[n][m]=(s[n][m]=='.');
	dfs(1,1);
	int siz=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]=='.')
				siz++;
	if(!gd[1][1])
	{
		printf("%lld\n",1ll*siz*(siz-1)/2);
		return 0;
	}
	int x=1,y=1;
	while(x!=n||y!=m)
	{
		col[x][y]=1;
		if(gd[x+1][y])
			x++;
		else
			y++;
	}
	col[n][m]=1;
	ll ans=0;
	x=1,y=1;
	while(x!=n||y!=m)
	{
		if(col[x][y])
			siz--,ans+=siz,col[x][y]=2;
		if(gd[x][y+1])
			y++;
		else
			x++;
	}
	siz--; ans+=siz; col[n][m]=2;
	x=1,y=1;
	int cnt=0;
	while(x!=n||y!=m)
	{
		cnt++;
		assert(cnt<=n+m+5);
		if(!col[x][y])
		{
			int xx=x+1,yy=y-1;
			while(!gd[xx][yy])
				xx++,yy--;
			int tx=xx,ty=yy;
			while(tx!=1||ty!=1)
			{
				if(col[tx][ty]==1)
					ans++;
				if(gd[tx-1][ty])
					tx--;
				else
					ty--;
			}
			tx=xx,ty=yy;
			while(tx!=n||ty!=m)
			{
				if(gd[tx][ty+1])
					ty++;
				else
					tx++;
				if(col[tx][ty]==1)
					ans++;
			}
		}
		if(gd[x][y+1])
			y++;
		else
			x++;
	}
	printf("%lld\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
...
...
...

output:

17

result:

ok 1 number(s): "17"

Test #2:

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

input:

3 3
.**
.*.
...

output:

15

result:

ok 1 number(s): "15"

Test #3:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #4:

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

input:

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

output:

66

result:

ok 1 number(s): "66"

Test #5:

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

input:

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

output:

1378

result:

ok 1 number(s): "1378"

Test #6:

score: -100
Time Limit Exceeded

input:

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

output:


result: