-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathCAOS2.c
107 lines (97 loc) · 3.15 KB
/
CAOS2.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<stdio.h>
#include<stdlib.h>
int R,C,buf,top[505][505],right[505][505],left[505][505],bottom[505][505];
char str[600][600];
int main(void)
{
int T;
scanf("%d",&T);
while(T--)
{
int count=0,i,j,L,RT,T,B,prime[501]={0,0,1,2,2,3,3,4,4,4,4,5,5,6,6,6,6,7,7,8,8,8,8,9,9,9,9,9,9,10,10,11,11,11,11,11,11,12,12,12,12,13,13,14,14,14,14,15,15,15,15,15,15,16,16,16,16,16,16,17,17,18,18,18,18,18,18,19,19,19,19,20,20,21,21,21,21,21,21,22,22,22,22,23,23,23,23,23,23,24,24,24,24,24,24,24,24,25,25,25,25,26,26,27,27,27,27,28,28,29,29,29,29,30,30,30,30,30,30,30,30,30,30,30,30,30,30,31,31,31,31,32,32,32,32,32,32,33,33,34,34,34,34,34,34,34,34,34,34,35,35,36,36,36,36,36,36,37,37,37,37,37,37,38,38,38,38,39,39,39,39,39,39,40,40,40,40,40,40,41,41,42,42,42,42,42,42,42,42,42,42,43,43,44,44,44,44,45,45,46,46,46,46,46,46,46,46,46,46,46,46,47,47,47,47,47,47,47,47,47,47,47,47,48,48,48,48,49,49,50,50,50,50,51,51,51,51,51,51,52,52,53,53,53,53,53,53,53,53,53,53,54,54,54,54,54,54,55,55,55,55,55,55,56,56,56,56,56,56,57,57,58,58,58,58,58,58,59,59,59,59,60,60,61,61,61,61,61,61,61,61,61,61,62,62,62,62,62,62,62,62,62,62,62,62,62,62,63,63,63,63,64,64,65,65,65,65,66,66,66,66,66,66,66,66,66,66,66,66,66,66,67,67,67,67,67,67,68,68,68,68,68,68,68,68,68,68,69,69,70,70,70,70,71,71,71,71,71,71,72,72,72,72,72,72,72,72,73,73,73,73,73,73,74,74,74,74,74,74,75,75,75,75,76,76,76,76,76,76,77,77,77,77,77,77,77,77,78,78,78,78,79,79,79,79,79,79,79,79,80,80,80,80,80,80,80,80,80,80,81,81,82,82,82,82,82,82,82,82,82,82,83,83,84,84,84,84,84,84,85,85,85,85,86,86,86,86,86,86,87,87,87,87,87,87,87,87,88,88,88,88,89,89,90,90,90,90,91,91,91,91,91,91,91,91,91,91,91,91,92,92,92,92,92,92,92,92,93,93,93,93,94,94,94,94,94,94,94,94,95,95};
scanf(" %d%d",&R,&C);
for(i=0;i<501;i++)
{
str[0][i]='#';
top[1][i]=0;
bottom[R][i]=0;
left[i][0]=0;
right[i][C-1]=0;
}
for(i=1;i<=R;i++)
scanf(" %s",str[i]);
for(i=1;i<=R;i++)
{
for(j=0;j<C;j++)
{
if(str[i][j]=='#')
{
top[i][j]=0;
left[i][j]=0;
}
else
{
if(i>1)
{
top[i][j]=top[i-1][j];
if(str[i-1][j]=='^')
top[i][j]++;
}
if(j>0)
{
left[i][j]=left[i][j-1];
if(str[i][j-1]=='^')
left[i][j]++;
}
}
if(str[i][C-j-1]=='#')
right[i][C-j-1]=0;
else if(j>0)
{
right[i][C-j-1]=right[i][C-j];
if(str[i][C-j]=='^')
right[i][C-j-1]++;
}
if(str[R-i+1][j]=='#')
bottom[R-i+1][j]=0;
else if(i>1)
{
bottom[R-i+1][j]=bottom[R-i+2][j];
if(str[R-i+2][j]=='^')
bottom[R-i+1][j]++;
}
}
}
buf=500;
for(i=3;i<R-1;i++)
{
for(j=2;j<C-2;j++)
{
if(str[i][j]=='^')
{
if(str[i-1][j]=='#' || str[i-2][j]=='#' || str[i+1][j]=='#' || str[i+2][j]=='#' || str[i][j-1]=='#' || str[i][j-2]=='#' || str[i][j+1]=='#' || str[i][j+2]=='#')
{}
else
{
L=left[i][j];
if(L<buf)
buf=L;
RT=right[i][j];
if(RT<buf)
buf=RT;
T=top[i][j];
if(T<buf)
buf=T;
B=bottom[i][j];
if(B<buf)
buf=B;
count=count+prime[buf];
buf=500;
}
}
}
}
printf("%d\n",count);
}
return 0;
}