首页 > 代码库 > UVa 572 Oil Deposits (Floodfill && DFS)

UVa 572 Oil Deposits (Floodfill && DFS)

2024-10-21 20:21:39   211人阅读

题意 ：输入一个m行n列的字符矩阵，统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻（横竖以及对角方向），就是说它们属于同一个八连块。

 

分析 ：可以考虑种子填充深搜的方法。两重for循环枚举所有的点，然后只要是@点且还没被染色过则从这个点出发到达相邻的点染成同样的色（这里的颜色可以用不同的数字来表示），然后每一块@的联通块都能通过这种方式求出来，详情可以参考Wiki百科的动画帮助理解=》http://en.widipedia.org/wiki/Floodfill

 

技术分享 
#include<bits/stdc++.h>
using namespace std;
int G[101][101], row, col, seed[101][101], ans = 0;
int Move[8][2] = {
    {-1,1},{0,1},{1,1},
    {-1,0},      {1,0},
   {-1,-1},{0,-1},{1,-1}
};
bool bound(int Row, int Col)
{
    if(Row<0 || Col<0 || Row>=row || Col>=col) return true;
    else return false;
}
int SEED = 1;
inline void DFS(int Row, int Col)
{
    if(!G[Row][Col]) return;
    else{
        seed[Row][Col] = SEED;
        for(int i=0; i<8; i++){
            int y = Row + Move[i][0];
            int x = Col + Move[i][1];
            if(!bound(y, x) && G[y][x] && seed[y][x]==0) DFS(y, x);
        }
    }
}
int main(void)
{
    while(~scanf("%d %d", &row, &col) && (row&&col)){
        for(int i=0; i<101; i++){
            memset(G[i], false, sizeof(G[i]));
            memset(seed[i], 0, sizeof(seed[i]));
        }
        SEED = 1;
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                char temp; scanf(" %c", &temp);
                if(temp==‘*‘) G[i][j] = false;
                else G[i][j] = true;
            }
        }
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(G[i][j] && seed[i][j]==0) {DFS(i, j);SEED++;}
            }
        }
        printf("%d\n", SEED-1);
    }
    return 0;
}
View Code

 

经验 ：在dfs中需要往八个方向进行搜索，之前的做法从多个if=》存到move数组利用for循环实现=》现在有一个更简便的方法=》

 for(int dr=-1; dr<=1; dr++)
      for(int dc=-1; dc<=1; dc++){
           int y = Row + dr;
           int x = Col + dc;
           if(!bound(y, x) && G[y][x] && seed[y][x]==0) DFS(y, x);
      }

 

UVa 572 Oil Deposits (Floodfill && DFS)


联系
我们