6 11_oil_deposit_uva572 - nuaazdh/acm GitHub Wiki

##例题6-11 油田（Oil Deposit UVa572） ###问题 一个由*和@构成的矩阵，位于相邻位置（横向、纵向或者对角）的@属于同一块油田，现在给定矩阵，输出油田的有多少块。

第一行m和n分别表示行数和列数，后面的 m行为矩阵的详细情况，以 0 0结束。

样例输入

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

样例输出

0
1
2
2

###分析 问题不复杂，找到一个@，然后将它置为*，然后遍历8个方向（注意判断越界），将相邻的@也置位，并递归相邻位置的的@的8个方向。用递归实现。

如何遍历8个方向，这个在棋盘问题中已经有过，通过数组存储方向的坐标增量。

###code in C

#include <stdio.h>

int dr[]={-1,-1,-1,0,0,1,1,1}, dc[]={-1,0,1,-1,1,-1,0,1};

#define MAX_SIZE 110

char deposit[MAX_SIZE][MAX_SIZE];


int is_valid_position(int m, int n, int i , int j)
{
    return (i>=0 && i<m && j>=0 && j<n);
}

void remove_one_deposit(int m, int n, int i, int j)
{
    int di,dj;
    if(!is_valid_position(m,n,i,j) || deposit[i][j]!='@')
        return;
    deposit[i][j] = '*';
    for (di = 0; di < 8; ++di) {
        for (dj = 0; dj < 8; ++dj) {
            if(is_valid_position(m,n,i+dr[di],j+dc[dj])){
                remove_one_deposit(m,n,i+dr[di],j+dc[dj]);
            }
        }
    }
}

int find_and_remove_deposit(int m, int n)
{
    int i,j,found=0;
    for (i = 0; i < m; ++i) {
        for (j = 0; j < n; ++j) {
            if(deposit[i][j]== '@') {
                found = 1;
                break;
            }
        }
        if(found) break;
    }
    if(!found) /* not found */
        return 0;
    remove_one_deposit(m,n,i,j);
    return 1;
}

void read_deposit(int m, int n)
{
    int i;
    for (i = 0; i < m; ++i) {
        scanf("%s",deposit[i]);
    }
}

void print_deposit(int m,int n)
{
    int i,j;
    for (i = 0; i < m; ++i) {
        for (j = 0; j < n; ++j) {
            printf("%c",deposit[i][j]);
        }
        printf("\n");
    }
}


int main()
{
    int row,col,cnt=0;
    while(scanf("%d%d", &row, &col) && row){
        read_deposit(row,col);
//        print_deposit(row,col);
        cnt = 0;
        while(find_and_remove_deposit(row,col)!=0) {
            cnt++;
//            print_deposit(row,col);
//            printf("\n\n");
        }
        printf("%d\n", cnt);
    }
    return 0;
}

###点评

  1. 递归实现比较清晰，但是效率不高；
  2. 这里直接对原数组进行了更改，如果不允许更改，则需要设置一个跟原来矩阵相同维数的标志矩阵，来标记已经访问过的单元格；

有没有可以读入一次，就可以判断完成的，直观上是有的，首先统计每一行的@，第一行不相邻的@的集合数，记为 count， 继续读入新行，如果新行有@将上一行的@连到一起，比如正好处于样例输入第二个第二行那样，则count--;，如果又出现一个与上一行的全部不相邻，count++。最后的直接输出count。 ###代码

⚠️ **GitHub.com Fallback** ⚠️