Google Codejam 2009 Квалификационная проблема: Watershed in C++

Question

Я опробовал this Codejam problem и создал действительное решение на C++. На сайте есть Python solution. Интересно, будут ли какие-либо люди C++ предлагать некоторые улучшения/оптимизации для этого решения. Благодаря!

BTW: В Codejam цель состоит в том, чтобы написать код как можно быстрее (причина, по которой Python был бы лучшим выбором языка), но я заинтересован в улучшении решения.

#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

Вот решение от самого быстрого (7 мин.) Участника на C. Очень кратким. Он даже не тратить время на использование пробел :)

#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] 
} 

Во-вторых, я хотел бы предложить вам не использовать тип вектора в конкурсе программирования, как это имеет тенденцию быть медленнее, чем использование массивов символов. То же самое со строковым типом. Попытайтесь придерживаться классических типов данных C, если структура данных C++ ДЕЙСТВИТЕЛЬНО сделает вашу жизнь проще.

В-третьих, не используйте одномерный массив, если вы можете использовать 2-й, делая сами умножения, возможно, все равно медленнее. В любом случае, это не принесет вам никакого преимущества.

В-четвертых, старайтесь избегать локальных переменных. Декларирование вещи, как:

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

локально может быть очень дорогим в конкурсе, тем более, что ваш находятся в петле. Это хорошая практика ПРОГРАММИРОВАНИЯ, но это плохо, если вы хотите каждый бит скорости, который вы можете получить.

Помимо этого теоретическая сложность - это O (строки x cols), которая является оптимальной.

Редактировать: Вы читаете цифры как строки? Нет, строковые потоки также медленны, просто читайте их как ints или используйте функцию C fread, если вы хотите иметь очень быстрое чтение.

Редактировать 2: избегать рекурсии! вы можете использовать очередь FIFO, которая сохраняет вашу позицию и, таким образом, избегать ваших рекурсивных вызовов. В основном, выполните поиск BF вместо текущего поиска DF. Посмотрите алгоритм Ли. Ответьте здесь: Change FloodFill-Algorithm to get Voronoi Territory for two data points?