Google Codejam 2009 Qualification Problem: Watershed in C ++

Question

I tried this Codejam problem and created a valid C ++ solution. There is a Python solution on the website . I wonder if any C ++ people will offer some improvements / optimizations for this solution. Thank!

BTW: In Codejam, the goal is to write code as quickly as possible (the reason Python would be the best choice of language), but I'm interested in improving the solution.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>

#include <assert.h>
#include <stdlib.h>

// Watershed Practice Problem
// http://code.google.com/codejam/contest/dashboard?c=90101#s=p1

using namespace std;

#ifdef DEBUG
static int running_time;
#endif

void SplitString(const string &s,
                 char delim,
                 vector<string> &elems) {
  stringstream ss(s);
  string item;
  while(getline(ss, item, delim)) {
    elems.push_back(item);
  }
}

void PrintMap(const char map[], int height, int width) {
    for (int i = 0; i < height; ++i) {
      for (int j = 0; j < width; ++j) {
        cout << map[(i * width) + j] << " "; 
      }
      cout << endl;
    }
}

void MinNeighbor(const int altitude_map[],
                 int height, int width,
                 int i, int j,
                 int & n_i, int & n_j) {
  int min_altitude = altitude_map[(i * width) + j];

  n_i = i;
  n_j = j;

  // North.
  if ((i - 1) >= 0
      && altitude_map[((i - 1) * width) + j] < min_altitude)  {
    min_altitude = altitude_map[((i - 1) * width) + j];
    n_i = i - 1;
    n_j = j;
  }
  // West.
  if ((j - 1) >= 0
      && altitude_map[(i * width) + (j - 1)] < min_altitude) {
    min_altitude = altitude_map[(i * width) + (j - 1)]; 
    n_i = i;
    n_j = j - 1;
  }
  // East.
  if ((j + 1) < width
      && altitude_map[(i * width) + (j + 1)] < min_altitude) {
    min_altitude = altitude_map[(i * width) + (j + 1)]; 
    n_i = i;
    n_j = j + 1;
  }
  // South.
  if ((i + 1) < height
      && altitude_map[((i + 1) * width) + j] < min_altitude)  {
    min_altitude = altitude_map[((i + 1) * width) + j];
    n_i = i + 1;
    n_j = j;
  } 
}

void Drain(const int altitude_map[],
           char label_map[],
           char & label,
           int height, int width,
           int i, int j) {
  int n_i = 0;
  int n_j = 0;

  MinNeighbor(altitude_map, height, width, i, j, n_i, n_j);

#ifdef DEBUG
  cout << endl;
  cout << "The min neighbor of : (" << i << "," << j << ") ";
  cout << "is (" << n_i << "," << n_j << ")" << endl;
#endif

  if (altitude_map[(n_i * width) + n_j] < altitude_map[(i * width) + j]) {
    // We are draining into an existing basin; use its label.
    if (label_map[(n_i*width) + n_j] != '-')
      label = label_map[(n_i*width) + n_j];
    else // Drain into the neighboring cell with the smallest altitude.
      Drain(altitude_map, label_map, label, height, width, n_i, n_j);
  }

  label_map[(i*width) + j] = label;

#ifdef DEBUG
  ++running_time;
#endif
}

int main(int argc, char *argv[]) {
  string file_name;
  if (argc < 2)
    file_name = "B-tiny-practice.in";
  else
    file_name = argv[1];

  ifstream input_file;
  input_file.open(file_name.c_str());

  assert(input_file.is_open());

  string line;
  // The first line contains the number of maps.
  getline(input_file, line); 

  int num_maps = atoi(line.c_str());
  int case_num = 1;

  while (case_num <= num_maps) {
    assert(!input_file.eof());

    getline(input_file, line);  // Line should have two numbers: W H.

    size_t delim = line.find(" ");
    int height = atoi(line.substr(0, delim).c_str());
    int width = atoi(line.substr(delim + 1).c_str());

    int altitude_map[height * width];
    char label_map[height * width];

    // Populate the altitude map and initialize the label map.
    for (int i = 0; i < height; ++i) {
      assert(!input_file.eof());
      getline(input_file, line);

      vector<string> row;
      SplitString(line, ' ', row); 

      int j = 0;
      for (vector<string>::const_iterator ci = row.begin(); 
          ci != row.end(); ++ci) {
        label_map[(i * width) + j] = '-';
        altitude_map[(i * width) + j++] = atoi(ci->c_str());
      }
    }

    char current_label = 'a';

    // Populate the labels.
    for (int i = 0; i < height; ++i) {
      for (int j = 0; j < width; ++j) {
        if (label_map[(i * width) + j] == '-') {
          char label = current_label;
          Drain(altitude_map, label_map, label, height, width, i, j);
          if (label == current_label)
            ++current_label;
        }
      }
    }

    cout << "Case #" << case_num++ << ":" << endl;
    PrintMap(label_map, height, width);

#ifdef DEBUG
    cout << endl << "Running Time: " << running_time << endl;
    running_time = 0;
#endif
  }

  input_file.close();

  return 0;
}

// vim:set sw=2 sts=2 ts=2:

Answer 1

Here is a solution from the fastest (7 minutes) participant in C. Very concise. He does not even waste time using Spacebar:)

#include<stdio.h>
#include<memory.h>
#include<string.h>
#define INF 999999
int n, m;
int a[128][128];
int path[128][128];
int dx[4]={-1, 0, 0, 1};
int dy[4]={0, -1, 1, 0};
int inv[4]={3, 2, 1, 0};
int ans[128][128], anscnt;
bool v[128][128];
void f1(int x, int y)
{
    v[x][y]=true; ans[x][y]=anscnt;
    int k, nx, ny;
    if(path[x][y]!=-1)
    {
        nx=x+dx[path[x][y]];
        ny=y+dy[path[x][y]];
        if(!v[nx][ny]) f1(nx, ny);
    }
    for(k=0;k<4;k++)
    {
        nx=x+dx[k]; ny=y+dy[k];
        if(nx<1 || ny<1 || nx>n || ny>m) continue;
        if(path[nx][ny]!=-1 && nx+dx[path[nx][ny]]==x && ny+dy[path[nx][ny]]==y && !v[nx][ny])
            f1(nx, ny);
    }
}
int main()
{
    char filename[32];
    char infile[32], outfile[32];
    scanf("%s", filename);
    strcpy(infile, filename); strcpy(outfile, filename);
    strcat(infile, ".in"); strcat(outfile, ".out");
    FILE *fp=fopen(infile, "r"), *ofp=fopen(outfile, "w");

    int t, tc;
    int i, j, k;
    int nx, ny;
    int mh, pt;
    fscanf(fp, "%d", &tc);
    for(t=1;t<=tc;t++)
    {
        fscanf(fp, "%d%d", &n, &m);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++) fscanf(fp, "%d", &a[i][j]);
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                mh=INF;
                path[i][j]=-1;
                for(k=0;k<4;k++)
                {
                    nx=i+dx[k]; ny=j+dy[k];
                    if(nx<1 || ny<1 || nx>n || ny>m) continue;
                    if(mh>a[nx][ny]){mh=a[nx][ny]; pt=k;}
                }
                if(mh>=a[i][j]) continue;
                path[i][j]=pt;
            }
        }
        anscnt=0;
        memset(v, false, sizeof(v));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(v[i][j]) continue;
                anscnt++; f1(i, j);
            }
        }
        fprintf(ofp, "Case #%d:\n", t);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<m;j++)
            {
                fprintf(ofp, "%c ", ans[i][j]+'a'-1);
            }
            fprintf(ofp, "%c\n", ans[i][m]+'a'-1);
        }
    }
    return 0;
} 

Answer 2

, , - , . , . , [X] [Y] . :

dx[] = {1, 0, 0 - 1};
dy[] = {0, -1, 1, 0};

, :

for ( i = 0; i < 4; ++i )
{
  newx = X + dx[i];
  newy = Y + dy[i];
  // [newx][newy] is a neighbour of [X][Y]
}

-, , , char. . C, ++ .

-, , 2- , , , . , , .

-, . , :

int altitude_map[height * width];
char label_map[height * width];

, , . , , , .

, - O ( x cols), .

: ? , , ints Fread, .

2: ! FIFO, , , . , BF DF. . : FloodFill-Algorithm, ?