比赛 |
暑假培训B班二测 |
评测结果 |
AAAAAAAA |
题目名称 |
劣质的草 |
最终得分 |
100 |
用户昵称 |
Citron酱 |
运行时间 |
0.097 s |
代码语言 |
C++ |
内存使用 |
15.61 MiB |
提交时间 |
2012-07-22 09:58:16 |
显示代码纯文本
#include <cstdio>
#define I_F "badgras.in"
#define O_F "badgras.out"
const int MAXn=1000+2;
const short R[8][2]={{ 1,-1},{ 1, 0},{ 1, 1},
{ 0,-1}, { 0, 1},
{-1,-1},{-1, 0},{-1, 1}};
struct stack
{
int x,y;
short r;
};
int n,m;
long map[MAXn][MAXn]={{0}};
long ans=0;
stack s[MAXn*MAXn];
void Input();
void Dfs(const int&, const int&);
void Search();
void Output();
int main()
{
Input();
Search();
Output();
return 0;
}
void Input()
{
freopen(I_F,"r",stdin);
scanf("%d%d",&n,&m);
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
scanf("%ld",&map[i][j]);
}
void Dfs(const int &x, const int &y)
{
// map[x][y]=0;
// for (short i=0; i<8; ++i)
// if (map[x+R[i][0]][y+R[i][1]]>0)
// Dfs(x+R[i][0], y+R[i][1]);
long top=1;
map[x][y]=0;
s[0].x=x;
s[0].y=y;
s[0].r=0;
bool flag;
while (top>0)
{
flag=true;
for (short i=s[top-1].r; i<8; ++i)
if (map[s[top-1].x+R[i][0]][s[top-1].y+R[i][1]]>0)
{
map[s[top-1].x+R[i][0]][s[top-1].y+R[i][1]]=0;
s[top-1].r=i+1;
s[top].x=s[top-1].x+R[i][0];
s[top].y=s[top-1].y+R[i][1];
s[top].r=0;
++top;
flag=false;
break;
}
if (flag)
--top;
}
}
void Search()
{
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
if (map[i][j]>0)
++ans,
Dfs(i,j);
}
void Output()
{
freopen(O_F,"w",stdout);
printf("%ld\n",ans);
}