2014-03-20 03:35

题目：实现画图的Flood Fill操作。

解法：DFS和BFS皆可，但BFS使用的队列在时间复杂度上常数项比较大，速度略慢，所以我选了DFS。当然，如果图很大的话DFS是会导致call stack溢出的，那就摊上事儿了。

代码：

1 // 9.7 Implement a flood fill painter that changes a certain area to a certain color. You are given one point as the seed. 2 #include 
     
       3 #include 
      
        4 using namespace std; 5  6 void floodFill(int i, int j, int n, int m, int new_color, vector
       
        
          > &canva) 7 { 8     int old_color = canva[i][j]; 9 10     canva[i][j] = new_color;11     if (i >= 1 && old_color == canva[i - 1][j]) {12         floodFill(i - 1, j, n, m, new_color, canva);13     }14     if (i <= n - 2 && old_color == canva[i + 1][j]) {15         floodFill(i + 1, j, n, m, new_color, canva);16     }17     if (j >= 1 && old_color == canva[i][j - 1]) {18         floodFill(i, j - 1, n, m, new_color, canva);19     }20     if (j <= m - 2 && old_color == canva[i][j + 1]) {21         floodFill(i, j + 1, n, m, new_color, canva);22     }23 }24 25 int main()26 {27     int i, j, c;28     int n, m;29     vector
         
          
            > canva;30 31 scanf("%d%d", &n, &m);32 canva.resize(n);33 for (i = 0; i < n; ++i) {34 canva[i].resize(m);35 }36 37 for (i = 0; i < n; ++i) {38 for (j = 0; j < m; ++j) {39 scanf("%d", &canva[i][j]);40 }41 }42 43 while (scanf("%d%d%d", &i, &j, &c) == 3) {44 if (i >= 0 && i <= n - 1 && j >= 0 && j <= m - 1) {45 floodFill(i, j, n, m, c, canva);46 }47 for (i = 0; i < n; ++i) {48 for (j = 0; j < m; ++j) {49 printf((j == 0 ? "%d" : " %d"), canva[i][j]);50 }51 printf("\n");52 }53 }54 55 for (i = 0; i < n; ++i) {56 canva[i].clear();57 }58 canva.clear();59 60 return 0; 61 }