QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#48567#3999. BpbBppbpBB13889577060#AC ✓69ms87852kbC++1.5kb2022-09-14 15:49:352022-09-14 15:49:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-14 15:49:37]
  • 评测
  • 测评结果:AC
  • 用时:69ms
  • 内存:87852kb
  • [2022-09-14 15:49:35]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int INF=1e9;
int n,m,cnt,tot,num[1005][1005],tt,dt[1000002],maxx[1000002],minx[1000002],maxy[1000002],miny[1000002];
char ch[1005][1005];
bool fl[1002][1002],bj[1000002];
void dfs(int x,int y){
	if (fl[x][y] || ch[x][y]!='.')return;
	if (x==1 || x==n || y==1 || y==m)bj[cnt]=1;
	fl[x][y]=1;num[x][y]=cnt;dt[cnt]++;
	minx[cnt]=min(minx[cnt],x);
	miny[cnt]=min(miny[cnt],y);
	maxx[cnt]=max(maxx[cnt],x);
	maxy[cnt]=max(maxy[cnt],y);
	if (x-1>=1)dfs(x-1,y);
	if (x+1<=n)dfs(x+1,y);
	if (y-1>=1)dfs(x,y-1);
	if (y+1<=m)dfs(x,y+1);
}
bool iskong(int num){
	return (maxx[num]-minx[num]==3 && maxy[num]-miny[num]==3 && dt[num]==12);
}
int main()
{
	for (int i=1;i<=1000000;i++)
	{
		maxx[i]=maxy[i]=-INF;
		minx[i]=miny[i]=INF;
	}
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)scanf("%s",ch[i]+1);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	if (!fl[i][j] && ch[i][j]=='.')
	{
		cnt++;dfs(i,j);
	}
	for (int i=1;i<=cnt;i++)if (!bj[i] && iskong(i))tt++;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=m;j++)
	if (!bj[num[i][j]] && ch[i][j]=='.' && iskong(num[i][j]))
	{
		if (i-4>=1 && ch[i-4][j]=='.' && iskong(num[i-4][j]))tot++;
		if (i+4<=n && ch[i+4][j]=='.' && iskong(num[i+4][j]))tot++;
		if (j-4>=1 && ch[i][j-4]=='.' && iskong(num[i][j-4]))tot++;
		if (j+4<=m && ch[i][j+4]=='.' && iskong(num[i][j+4]))tot++;
	}
	printf("%d %d\n",tot/4,tt-tot/2);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 22128kb

input:

10 17
#################
#################
#################
####..#####..####
###....###....###
###....###....###
####..#####..####
#################
#################
#################

output:

1 0

result:

ok single line: '1 0'

Test #2:

score: 0
Accepted
time: 3ms
memory: 22188kb

input:

14 11
.##########
.##########
.##########
.####..####
.###....###
.###....###
.####..####
.##########
.##########
.##########
.###.......
.###.......
.###.......
.###.......

output:

0 1

result:

ok single line: '0 1'

Test #3:

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

input:

20 14
.##########...
.##########...
.##########...
.####..####...
.###....###...
.###....###...
.####..####...
.##########...
.##########...
.##########...
.#############
.#############
.#############
.#######..####
....###....###
....###....###
....####..####
##############
##############
#########...

output:

0 2

result:

ok single line: '0 2'

Test #4:

score: 0
Accepted
time: 5ms
memory: 22152kb

input:

1 1
.

output:

0 0

result:

ok single line: '0 0'

Test #5:

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

input:

50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..........................................

output:

4 1

result:

ok single line: '4 1'

Test #6:

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

input:

50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..........................................

output:

3 7

result:

ok single line: '3 7'

Test #7:

score: 0
Accepted
time: 30ms
memory: 34804kb

input:

1000 1000
...................###.......................................................##########................##########.###.............................................................##############.............................#################..............................#################........

output:

1621 2804

result:

ok single line: '1621 2804'

Test #8:

score: 0
Accepted
time: 28ms
memory: 35348kb

input:

1000 1000
.....##############.....................................................................................##############.....................................##############...................................##########...................................................................#########...

output:

0 5024

result:

ok single line: '0 5024'

Test #9:

score: 0
Accepted
time: 25ms
memory: 35712kb

input:

1000 1000
.....................................................................................................................................................................................................................................................#################...............................

output:

3629 0

result:

ok single line: '3629 0'

Test #10:

score: 0
Accepted
time: 28ms
memory: 34844kb

input:

1000 1000
........................................##########...............................................................................##########..........................................................................................................................................................

output:

944 3746

result:

ok single line: '944 3746'

Test #11:

score: 0
Accepted
time: 27ms
memory: 35036kb

input:

1000 1000
...................................................................................#################........##############......................................................................................................................................................##############.......

output:

2305 1903

result:

ok single line: '2305 1903'

Test #12:

score: 0
Accepted
time: 40ms
memory: 58788kb

input:

1000 1000
...........................................................................................................................................................##########................................................................................................................................

output:

258 523

result:

ok single line: '258 523'

Test #13:

score: 0
Accepted
time: 51ms
memory: 60296kb

input:

1000 1000
.....................................................................................................................................................................................................................................................................................................

output:

539 235

result:

ok single line: '539 235'

Test #14:

score: 0
Accepted
time: 39ms
memory: 87852kb

input:

1000 1000
.....................................................................................................................................................................................................................................................................................................

output:

0 1

result:

ok single line: '0 1'

Test #15:

score: 0
Accepted
time: 69ms
memory: 87144kb

input:

1000 1000
.....................................................................................................................................................................................................................................................................................................

output:

1 0

result:

ok single line: '1 0'

Test #16:

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

input:

100 1000
###################################################################################################################################################################################################################################################################################################...

output:

500 0

result:

ok single line: '500 0'

Test #17:

score: 0
Accepted
time: 7ms
memory: 22224kb

input:

100 1000
###################################################################################################################################################################################################################################################################################################...

output:

580 0

result:

ok single line: '580 0'

Test #18:

score: 0
Accepted
time: 2ms
memory: 22536kb

input:

100 1000
###################################################################################################################################################################################################################################################################################################...

output:

0 700

result:

ok single line: '0 700'

Test #19:

score: 0
Accepted
time: 2ms
memory: 22272kb

input:

100 1000
###################################################################################################################################################################################################################################################################################################...

output:

0 710

result:

ok single line: '0 710'

Test #20:

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

input:

100 1000
###################################################################################################################################################################################################################################################################################################...

output:

0 700

result:

ok single line: '0 700'

Test #21:

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

input:

100 1000
##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....

output:

0 710

result:

ok single line: '0 710'

Test #22:

score: 0
Accepted
time: 2ms
memory: 22292kb

input:

100 1000
###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......#...

output:

0 700

result:

ok single line: '0 700'

Test #23:

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

input:

100 1000
###################################################################################################################################################################################################################################################################################################...

output:

0 710

result:

ok single line: '0 710'

Test #24:

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

input:

100 1000
.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###....

output:

0 700

result:

ok single line: '0 700'

Test #25:

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

input:

100 1000
....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....#######...

output:

0 710

result:

ok single line: '0 710'

Test #26:

score: 0
Accepted
time: 21ms
memory: 36356kb

input:

1000 1000
##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##########..##...

output:

4316 0

result:

ok single line: '4316 0'

Test #27:

score: 0
Accepted
time: 25ms
memory: 35728kb

input:

1000 1000
##############..##############..##############..##############..##############..##############..##############..##############..##############..##############..##############..##############..##############..##############..##############..##############..##############..##############..##...

output:

0 5146

result:

ok single line: '0 5146'

Test #28:

score: 0
Accepted
time: 8ms
memory: 25084kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

5800 0

result:

ok single line: '5800 0'

Test #29:

score: 0
Accepted
time: 6ms
memory: 26456kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

5800 0

result:

ok single line: '5800 0'

Test #30:

score: 0
Accepted
time: 10ms
memory: 25536kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

0 7100

result:

ok single line: '0 7100'

Test #31:

score: 0
Accepted
time: 16ms
memory: 25452kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

0 7100

result:

ok single line: '0 7100'

Test #32:

score: 0
Accepted
time: 11ms
memory: 25984kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

0 7100

result:

ok single line: '0 7100'

Test #33:

score: 0
Accepted
time: 10ms
memory: 25508kb

input:

1000 1000
##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########...

output:

0 7100

result:

ok single line: '0 7100'

Test #34:

score: 0
Accepted
time: 14ms
memory: 25396kb

input:

1000 1000
###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###..........

output:

0 7100

result:

ok single line: '0 7100'

Test #35:

score: 0
Accepted
time: 9ms
memory: 25588kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

0 7100

result:

ok single line: '0 7100'

Test #36:

score: 0
Accepted
time: 11ms
memory: 25160kb

input:

1000 1000
.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###.......###...

output:

0 7100

result:

ok single line: '0 7100'

Test #37:

score: 0
Accepted
time: 5ms
memory: 25508kb

input:

1000 1000
....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....##########....######...

output:

0 7100

result:

ok single line: '0 7100'