https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=513

终于开始接触图了，恩，开始接触DFS了，这道题就是求连通分量，比较简单。

1 #include
     
       2 #include
      
        3 using namespace std; 4  5 int m, n;                                               //记录连通块的数量 6 char a[10000][10000]; 7 int  b[10000][10000]; 8  9 void DFS(int i, int j, int count)10 {11     if (i < 0 || i >= m || j < 0 || j >= n) return;     //在递归时出界的情况12         if(b[i][j]>0 || a[i][j]!='@')  return;13     b[i][j] = count;14     for (int p = -1; p <= 1; p++)15     {16         for (int q = -1; q <= 1; q++)17         {18             if (p != 0||q != 0)  DFS(i + p, j + q, count);19         }20     }21 }22 23 int main()24 {25     while (cin >> m >> n && m && n)26     {27         for (int i = 0; i < m; i++)28             scanf("%s", &a[i]);29         int count = 0;30         memset(b, 0, sizeof(b));31         for (int i = 0; i < m; i++)32         {33             for (int j = 0; j < n; j++)34             {35                 if (b[i][j] == 0 && a[i][j]=='@') DFS(i, j, ++count);36             }37         }38         cout << count << endl;39     }40     return 0;41 }
      
     

2016-12-03  07:49:56