hdu 1241 油田 裸DFS
题意：@代表油田 8个方向上还有@就相连 相当于求图中连通子图的个数
Sample Input
1 1 // n m
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output
0
1
2
2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std; int d[][] = {{,},{,-},{,},{,-},{,},{-,},{-,-},{-,}};
char map[][] ; int n , m ; void dfs(int x , int y)
{
int fx , fy ;
int i ;
map[x][y] = '*' ;
for (i = ; i < ; i++)
{
fx = x + d[i][] ;
fy = y + d[i][] ;
if (fx>= && fx<n && fy>= && fy<m && map[fx][fy] == '@')
{
dfs(fx,fy) ;
}
}
} int main()
{
//freopen("in.txt","r",stdin) ; while (scanf("%d %d" , &n , &m) !=EOF)
{
if (n == && m == )
break ;
int i , j ; for (i = ; i < n ; i++)
{
for (j = ; j < m ; j++)
{
cin>>map[i][j]; //用scanf一直WA=.=
} }
int sum = ;
for (i = ; i < n ; i++)
for (j = ; j < m ; j++)
{
if (map[i][j] == '@')
{
sum++ ; dfs(i,j) ;
}
}
printf("%d\n" , sum) ; } return ;
}
hdu 2952
上下左右 4个方向相连 求连通子图的个数
Sample Input
2
4 4
#.#. //#能走
.#.#
#.##
.#.#
3 5
###.#
..#..
#.###
Sample Output
6
3
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std; int d[][] = {{,},{,-},{,},{-,}};
char map[][] ; int n , m ; void dfs(int x , int y)
{
int fx , fy ;
int i ;
map[x][y] = '.' ;
for (i = ; i < ; i++)
{
fx = x + d[i][] ;
fy = y + d[i][] ;
if (fx>= && fx<n && fy>= && fy<m && map[fx][fy] == '#')
{
dfs(fx,fy) ;
}
}
} int main()
{
// freopen("in.txt","r",stdin) ;
int T ;
scanf("%d" , &T) ; while (T--)
{
scanf("%d %d" , &n , &m) ;
if (n == && m == )
break ;
int i , j ; for (i = ; i < n ; i++)
{
for (j = ; j < m ; j++)
{
cin>>map[i][j];
} }
int sum = ;
for (i = ; i < n ; i++)
for (j = ; j < m ; j++)
{
if (map[i][j] == '#')
{
sum++ ;
dfs(i,j) ;
}
}
printf("%d\n" , sum) ; } return ;
}
hdu 1312 能走多少格 裸DFS
Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#......... //.能走 #不能走 @起点
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
Sample Output
45
59
6
13
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std; int d[][] = {{,},{,-},{,},{-,} } ;
char map[][] ; int n , m ;
int sum = ; void dfs(int x , int y)
{
int fx , fy ;
int i ;
sum++ ;
map[x][y] = '#';
for (i = ; i < ; i++)
{
fx = x + d[i][] ;
fy = y + d[i][] ;
if (fx>= && fx<n && fy>= && fy<m && map[fx][fy] == '.')
{
dfs(fx,fy) ;
}
}
} int main()
{
// freopen("in.txt","r",stdin) ; while (scanf("%d %d" , &m , &n) !=EOF)
{
if (n == && m == )
break ;
int i , j ;
int bx , by ;
sum = ; for (i = ; i < n ; i++)
{
for (j = ; j < m ; j++)
{
cin>>map[i][j];
} }
for (i = ; i < n ; i++)
{
for (j = ; j < m ; j++)
{
if (map[i][j] == '@')
{
bx = i ;
by = j ;
}
} } dfs(bx,by) ; printf("%d\n" , sum) ; } return ;
}