Hatena::Grouptopcoder

cou929のTopCoder日記

2009-09-16

2003 TCO Semifinals 4

17:46

Dynamic Programming: From novice to advancedからの練習問題。

Easy - AvoidRoads

幅width, 高さheightのグリッド状の区画がある。位置(0, 0)から(width, height)まで、ちょうどwidth+heightステップで行きたい(1マス進むことを1ステップとする)。また、一部通行止めのルートがあり、それも与えられる。この条件のもと、スタートからゴールへのルートは何通りあるか。

width+heightステップと限定されていることで、進む方向が2種類に限定されるので、ほぼチュートリアルの例題と同じ問題になっている。

しょうもないミスで時間を使ってしまう。ひとつは、引数をクラス内の別の関数から使えるようにしようとして、publicのメンバ変数を作って、関数の最初にそこに代入するようにしたが、代入前のメンバ変数を使ってしまい、bus errorがでまくっていた。なんとも情けないミス。

class AvoidRoads {
public:
  width;
  height;

  long long numWays(int _width, int _height, vector <string> _bad)
  {
    dp[width][height];  // error
    width = _width;
    height = _height;
  
    // ...
  }
};

あとは、あるルートがbad指定されているかを判定する関数を作ったが、trueとfalseを逆に返していた。

class AvoidRoads {
public:
  int height;
  int width;
  vector <vector <int> > bad;

  int toInt(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}
  vector <int> split(const string _s, const string del)
  {
    vector <int> ret;
    string s = _s;

    while (!s.empty())
      {
	size_t pos = s.find(del);
	string sub = "";
	sub = s.substr(0, pos);
	ret.push_back(toInt(sub));
	if (pos != string::npos)
	  pos += del.size();
	s.erase(0, pos);
      }

    return ret;
  }

  bool isBad(int sw, int sh, int dw, int dh)
  {
    for (unsigned int i=0; i<bad.size(); i++)
      if ((sw == bad[i][0] && sh == bad[i][1] && dw == bad[i][2] && dh == bad[i][3]) || 
	  (sw == bad[i][2] && sh == bad[i][3] && dw == bad[i][0] && dh == bad[i][1]))
	return true;
    return false;
  }

  bool isInRange(int w, int h)
  {
    bool ret = false;
    if (0 <= w && w <= width && 0 <= h && h <= height)
      ret= true;
    return ret;
  }

  long long numWays(int _width, int _height, vector <string> _bad)
  {
    height = _height;
    width = _width;
    long long dp[width+1][height+1];

    for (unsigned int i=0; i<_bad.size(); i++)
      {
	vector <int> elm = split(_bad[i], " ");
	bad.push_back(elm);
      }

    for (int i=0; i<=width; i++)
      for (int j=0; j<=height; j++)
	dp[i][j] = 0;

    dp[0][0] = 1;

    for (int i=0; i<=width; i++)
      for (int j=0; j<=height; j++)
	{
	  long long counter = dp[i][j];
	  if (isInRange(i-1, j) && !isBad(i-1, j, i, j))
	    counter += dp[i-1][j];
	  if (isInRange(i, j-1) && !isBad(i, j-1, i, j))
	    counter += dp[i][j-1];
	  dp[i][j] = counter;
	}

    return dp[width][height];
  }
};