NYOJ27水池数目（BFS，DFS）

2
3 4
1 0 0 0 
0 0 1 1
1 1 1 0
5 5
1 1 1 1 0
0 0 1 0 1
0 0 0 0 0
1 1 1 0 0
0 0 1 1 1

2
3

AC代码：

BFS:

#include
#include 
int s,t,a[101][101];
int dx[4]={0,0,1,-1};//**四个方向搜索**//
int dy[4]={1,-1,0,0};
void bfs(int x,int y)
{
a[x][y]=0; 
    for(int k=0;k<4;k++)
    {
s=x+dx[k];
t=y+dy[k];
       if(a[s][t]==1)
{
bfs(s,t);
}
    }
}
int main()
{
int ncases,n,m,i,j,count;
    scanf("%d",&ncases);
    while(ncases--)
    {
count=0;
        scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++) 
{
scanf("%d",&a[i][j]);
}
}
    for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]==1)
{
bfs(i,j);
        count++;
}
}
}
    printf("%d\n",count);   
} 
    return 0;
}
                

#include
#include
const int N=100;
using namespace std;
int n,m;
int map[N][N];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
void dfs(int si,int sj)
{
map[si][sj] = 0;//没有必要回溯，
int di,i,j;
for(di=0;di<4;di++)
{
i = si + dir[di][0];
j = sj + dir[di][1];
if (i>=0 &&i=0 && jdfs(i,j);
}
}
int main()
{
int t,cnt;
cin>>t;
while(t--)
{
cin>>m>>n;
int i,j;
for(i=0;ifor(j=0;jcin>>map[i][j];
cnt = 0;
for(i=0;ifor(j=0;jif (map[i][j]==1)
{
cnt++;
dfs(i,j);
}
cout<}
return 0;
}