Project Euler task 81

#include <iostream>
#include <fstream>
#include <vector>
#include <string>

#define SIZE 80

using namespace std;

template<class CharType, class SeparatorType>
void split(const std::basic_string<CharType>& source, SeparatorType sep, std::vector<std::basic_string<CharType> >& ret, bool keepEmpty = false)
{
  ret.clear();
  size_t start = 0;
  size_t end;

  while((end = source.find(sep, start)) != std::basic_string<CharType>::npos)
  {
    if(start != end || keepEmpty)
    {
      ret.push_back(source.substr(start, end - start));
    }
    start = end + 1;
  }
  if(start != source.size() || keepEmpty)
  {
    ret.push_back(source.substr(start));
  }
}

int main(int argc, char** argv)
{
  int data[SIZE][SIZE];

  if (argc != 2)
    return -1;

  fstream f(argv[1]);
  string s;

  // Initialize data.
  for (int i = 0; i < SIZE; i++)
  {
    f >> s;
    vector<string> res; split(s, ',', res);

    for (int j = 0; j < res.size(); ++j)
    {
      data[i][j] = atoi(res[j].c_str());
    }
  }

  // Process the diagonal "rows".
  for (int i = 0; i < 2 * SIZE; i++)
  {
    int x = 0;
    int calc = 0;
    for (int y = i; y >= 0; --y)
    {
      bool minInit = false;

      if (x < SIZE && x >= 0 && y < SIZE)
      {
        int min = 0;
        int xPL = x - 1;
        int yPL = y;
        if (xPL >= 0 && yPL >= 0)
        {
          min = data[xPL][yPL];
          minInit = true;
        }

        int xPR = x;
        int yPR = y - 1;
        if (xPR >= 0 && yPR >= 0 && ((data[xPR][yPR] < min && minInit == true) || (minInit == false)))
        {
          min = data[xPR][yPR];
          minInit = true;
        }

        data[x][y] += min;
      }

      ++x;
    }
  }

  cout << data[SIZE-1][SIZE-1] << endl;

  return 0;
}

Comments

Unknown said…
OMG. This is simple Dijkstra problem, whic should me solved in 10 lines

Popular Posts