首页 > 搜索 > DFS搜索 > HDU 3329-The Flood-DFS-[解题报告]HOJ
2014
03-16

HDU 3329-The Flood-DFS-[解题报告]HOJ

The Flood

问题描述 :

Global warming has us all thinking of rising oceans ― well, maybe only those of us who live near the ocean. The small island nation of Gonnasinka has employed you to answer some questions for them. In particular they want to know how high the water has to get before their island becomes two islands (or more).

Given a grid of integers giving the altitudes of the island, how high must the ocean rise before the land splits into pieces?

输入:

Each test case begins with a line containing two positive integers n, m giving the dimensions of the igrid, then n lines each containing m positive integers. The integers indicate the original altitude of the grid elements. Grid elements are considered to be adjacent only if they share a horizontal or vertical edge. Values of zero (0) along the perimeter, and all zero cells connected to these, are ocean at its initial level. Cells of 0 not connected to the perimeter (that is, surrounded by higher land) are simply sea level elevations. Furthermore, assume the ocean initially surrounds the given grid. The island is initially connected. Neither n nor m will exceed 100 and heights will never exceed 1000. A line with 0 0 follows the last test case.

输出:

Each test case begins with a line containing two positive integers n, m giving the dimensions of the igrid, then n lines each containing m positive integers. The integers indicate the original altitude of the grid elements. Grid elements are considered to be adjacent only if they share a horizontal or vertical edge. Values of zero (0) along the perimeter, and all zero cells connected to these, are ocean at its initial level. Cells of 0 not connected to the perimeter (that is, surrounded by higher land) are simply sea level elevations. Furthermore, assume the ocean initially surrounds the given grid. The island is initially connected. Neither n nor m will exceed 100 and heights will never exceed 1000. A line with 0 0 follows the last test case.

样例输入:

5 5
3 4 3 0 0
3 5 5 4 3
2 5 4 4 3
1 3 0 0 0
1 2 1 0 0
5 5
5 5 5 5 7
4 1 1 1 4
4 1 2 1 3
7 1 0 0 4
7 3 4 4 4
0 0

样例输出:

Case 1: Island never splits.
Case 2: Island splits when ocean rises 3 feet.

#include "stdio.h"
#include "string.h"

#define MIN(a, b) ((a)<(b)?(a):(b))

int n, m;
int map[100][100];
int over[100][100];
int h;
int all;

int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void init(){
	int i, j;
	h = 0;
	for(i=0; i<n; i++)
		for(j=0; j<m; j++){
			scanf("%d", &map[i][j]);
			if(map[i][j]>h)
				h = map[i][j];
		}
}

int border(int* u, int* v, int l){
	int i, j;

	for(i=0; i<n; i++){
		if(!over[i][0] && l >= map[i][0]){
			*u = i;
			*v = 0;
			return 1;
		}
		if(!over[i][m-1] && l >= map[i][m-1]){
			*u = i;
			*v = m-1;
			return 1;
		}
	}

	for(j=0; j<m; j++){
		if(!over[0][j] && l >= map[0][j]){
			*u = 0;
			*v = j;
			return 1;
		}
		if(!over[n-1][j] && l >= map[n-1][j]){
			*u = n-1;
			*v = j;
			return 1;
		}
	}

	return 0;
}

void DFS(int u, int v, int l){
	int i;
	int nu, nv;
	over[u][v] = 1;
	all--;
	for(i=0; i<4; i++){
		nu = u + d[i][0];
		nv = v + d[i][1];
		if(nu>=0 && nv>=0 && nu<n && nv<m && map[nu][nv]<=l && !over[nu][nv])
			DFS(nu, nv, l);
	}
}

void DFS_N(int u, int v){
	int i;
	int nu, nv;
	over[u][v] = 1;
	all--;
	for(i=0; i<4; i++){
		nu = u + d[i][0];
		nv = v + d[i][1];
		if(nu>=0 && nv>=0 && nu<n && nv<m && !over[nu][nv])
			DFS_N(nu, nv);
	}
}

void main(){
	int c;
	int i, j;
	int u, v;
	int k;
	int mark;

	freopen("in.txt", "r", stdin);

	c = 0;
	while(scanf("%d %d", &n, &m), n+m){
		c++;
		init();
		all = 0;
		for(k=0; k<h; k++){
			memset(over, 0, sizeof(over));
			all = n*m;
			while(border(&u, &v, k))
				DFS(u, v, k);
			mark = 0;
			for(i=0; i<n; i++){
				for(j=0; j<m; j++)
					if(!over[i][j]){
						mark = 1;
						break;
					}
				if(mark)
					break;
			}
			if(mark)
				DFS_N(i, j);
			if(all)
				break;
		}
		
		if(all)
			printf("Case %d: Island splits when ocean rises %d feet.", c, k);
		else
			printf("Case %d: Island never splits.", c);
		printf("\n");
	}
}

Flood Fill

不容易,以前写稍麻烦的DFS总是漏洞百出,这次比较顺利,The Flood……

 

 

参考:http://blog.csdn.net/chaoojie/article/details/7532714


,
  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }