Google Codejam 2009 Problème de qualification: bassin hydrographique en C++

Question

J'ai essayé this Codejam problem et j'ai produit une solution valide en C++. Il y a un Python solution sur le site Web. Se demandait si des personnes C++ offriraient des améliorations/optimisations à cette solution. Merci!

BTW: Dans Codejam le but est d'écrire du code aussi vite que possible (une raison pour laquelle Python aurait été un meilleur choix de langue) mais je suis intéressé par l'amélioration de la 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

Voici la solution du concurrent le plus rapide (7 minutes) en C. Très concis. Il ne prend même pas le temps d'utiliser le :) barre d'espace

#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

Une façon de rendre le code plus agréable est d'utiliser ce que j'appelle des vecteurs de direction. Je ne sais pas s'il y a un nom pour eux dans la littérature ou non. Supposons que vous êtes à une position [X] [Y] et que vous souhaitiez lister ses voisins. Considérez:

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

Maintenant, cela vous donnera les voisins afin que demandé par le problème:

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

En second lieu, je vous suggère d'éviter d'utiliser le type de vecteur dans un concours de programmation, comme a tendance à être plus lent que d'utiliser des tableaux de char. Idem avec le type de chaîne. Essayez de vous en tenir aux types de données C classiques à moins qu'une structure de données C++ ne vous simplifie vraiment la vie. Troisièmement, n'utilisez pas un tableau unidimensionnel quand vous pourriez utiliser un 2d, faire les multiplications vous-même est probablement plus lent de toute façon. Cela ne va certainement pas vous procurer un avantage de toute façon.

Quatrièmement, essayez d'éviter les variables locales. les choses aiment déclarant:

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

peut être très coûteux dans un concours local, d'autant plus que les vôtres sont dans une boucle. C'est une bonne pratique de PROGRAMMATION, mais c'est mauvais si vous voulez tout ce que vous pouvez obtenir.

À part cela, la complexité théorique est O (rangées x cols), ce qui est optimal. Editer: lisez-vous les nombres sous forme de chaînes?

Non, les strings sont aussi lents, il suffit de les lire comme ints ou d'utiliser la fonction C fread si vous voulez avoir une lecture vraiment rapide.

Édition 2: éviter la récursivité! vous pouvez utiliser une file d'attente FIFO qui stocke votre position et évite ainsi vos appels récursifs. Fondamentalement, faites une recherche BF au lieu de votre recherche DF actuelle. Recherchez l'algorithme de Lee. Vérifiez ma réponse ici: Change FloodFill-Algorithm to get Voronoi Territory for two data points?