// Tflood.cc // ecna2009 // problem E - The Flood #include using namespace std; const int MAX = 200; const int BIG = 1000001; int m, n, Alt[MAX+1][MAX+1], Water[MAX+1][MAX+1], Mark[MAX+1][MAX+1]; int Min; void GetGrid(int m, int n){ for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>Alt[i][j]; for(int j=0;j<=n+1;j++) Alt[0][j]=Water[0][j]=Alt[m+1][j]=Water[m+1][j]=0; for(int i=1; i<=m;i++) Alt[i][0]=Water[i][0]=Alt[i][n+1]=Water[i][n+1]=0; //init Water[][] - not ocean as far as we know for(int i=1;i<=m;i++) for(int j=1;j<=n+1; j++) Water[i][j]=1; } void ZeroOutMark(int m,int n){ for(int i=0; i<=m+1; i++) for(int j=0; j<=n+1; j++) Mark[i][j]=0; // mark as "not yet visited" } void Flood(int i, int j){ if(Mark[i][j]==0){ Mark[i][j]=1; if(Alt[i][j]<=0){ //flood this spot Water[i][j]=Alt[i][j]=0; if(i>0) Flood(i-1,j); if(i<=m) Flood(i+1,j); if(j>0) Flood(i,j-1); if(j<=n) Flood(i,j+1); } } } // for debugging void PrintGrids(int m, int n){ cout<<"Alt[][] Water[][] Mark[][]"<0) Min = FindMin(i-1,j); if(i<=m) Min = FindMin(i+1,j); if(j>0) Min = FindMin(i,j-1); if(j<=n) Min = FindMin(i,j+1); } return Min; } void Decrement(int Min, int m, int n){ for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(Water[i][j]>0) Alt[i][j] -= Min; } void FillLand(int i, int j){ // know Water[i][j]==1 (is land) Mark[i][j]=1; if (Water[i-1][j] && Mark[i-1][j]==0) FillLand(i-1,j); if (Water[i+1][j] && Mark[i+1][j]==0) FillLand(i+1,j); if (Water[i][j-1] && Mark[i][j-1]==0) FillLand(i,j-1); if (Water[i][j+1] && Mark[i][j+1]==0) FillLand(i,j+1); } // check if disconnected bool TwoPieces(int m, int n){ //find some land (we know there's some) int i=1, j=1; while(Water[i][j]==0){ j++; if(j>n) { i++; j=1;} } //[i][j] is land FillLand(i,j); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(Mark[i][j]==0 && Water[i][j]) return true; return false; } int main(){ int CaseNo=1, height; bool Done; cin>>m>>n; while(m>0){ Done = false; GetGrid(m,n); ZeroOutMark(m,n); Flood(0,0); height = 0; while (!Done){ Min = BIG; ZeroOutMark(m,n); Min = FindMin(0,0); if(Min==BIG){ // all underwater cout<<"Case "<>m>>n; } return 0; }