SRM 646 Div2 Medium TheGridDivTwo

問題

SRM 646 - TopCoder Wiki

  • 2次元平面上の(0, 0)にいる.
  • 1秒で上下左右のどちらかに移動できる.
  • 移動できないポイントがブロックリストとして与えられている.
  • k秒で到達できる最大のx座標を答える問題

解答

  • 移動方法は沢山あるが,ブロックリストは高々50なのでそれほど多くない. つまり複雑な経路は存在しない(と考えた)
  • あとkが小さい
  • x座標方向に移動する優先度を最大にして,深さ優先してメモ化.

div1の問題も同様に解けるかなと考えたが,そっちはkが大きくて駄目だった.

そんなに甘くない(´・ω・`)

using namespace std;

class TheGridDivTwo
{
public:
  int find(vector <int> x, vector <int> y, int k)
    {
      // vector<int> dx = {1, 0, 0, -1};
      // vector<int> dy = {0, 1, -1, 0};
      vector<int> dx = {-1, 0, 0, 1};
      vector<int> dy = {0, 1, -1, 0};
      typedef pair<int, int> point;
      int i;
      map<point, int> visited;
      for (i = 0; i < x.size(); i++) {
        visited[make_pair(x[i], y[i])] = 2000;
      }
      // stack<int> z;
      // z.push(3);
      stack<pair<pair<int, int>, int> > s;
      s.push(make_pair(make_pair(0, 0), k));
      int res = 0;
      while (!s.empty()) {
        point p = s.top().first;
        int limit = s.top().second;
        s.pop();
        if (visited.find(p) != visited.end() && visited[p] >= limit) continue;
        visited[p] = limit;
        if (p.first + limit < res) continue;
        // cout << "(" << p.first << "," << p.second << "), " << limit << endl;
        res = max(res, p.first);
        if (limit == 0) continue;
        for (i = 0; i < dx.size(); i++) {
          point new_point = make_pair(p.first + dx[i], p.second + dy[i]);
          s.push(make_pair(new_point, limit - 1));
        }
      }
      return res;
    }
};