QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#48567 | #3999. BpbBppbpBB | 13889577060# | AC ✓ | 69ms | 87852kb | C++ | 1.5kb | 2022-09-14 15:49:35 | 2022-09-14 15:49:37 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'