题目链接

题意

输入一个m行n列的棋盘，棋盘上每个位置为'*'或者'@'，求'@'的连通块有几个（连通为8连通，即上下左右，两条对角线）。

思路

floodfill问题，用dfs解决。

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 const int N = 110; 7 char grid[N][N]; 8 int visit[N][N]; 9 int dir[8][2] = {   //八个邻接点10                     {
   1, 0}, {-1, 0}, {
   0, 1}, {
   0, -1},11                     {-1, -1}, {-1, 1}, {
   1, 1}, {
   1, -1}12                 };13 int m, n;14 15 void dfs(int r, int c)16 {17     for(int i=0; i<8; i++)18     {19         int nr = r+dir[i][0];20         int nc = c+dir[i][1];21 22         if(nr>=0 && nr
        
         =0 && nc
         
          >m>>n && m)34     {35         for(int i=0; i
          
           >grid[i];37 38 memset(visit, 0, sizeof(visit));39 int cnt = 0;40 for(int i=0; i