2014
03-16

# 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

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;
}