2006年国内予選C問題(Hexerpents of Hexwamp)(2007/07/25(水) 01:04:31)

2006年ICPC国内予選のC問題を暇なので解いてみた！

後から思ったんやけど、幅優先の方がいいね・・・
実際にコレ実行したら結構時間かかるし（汗
でも、絶対にどこか枝刈りで切るはずだ！！

本日のコーディングミス

こんな酷いミス久しぶりww
何回か、コード見直したのに全く気づかなかった

bool isHit(int x, int y){
  for(int i = 0; i < node.size(); i++){
    if(x == node[0].x && y == node[0].y){
      return true;
    }
  }
  for(int i = 0; i < block.size(); i++){
    if(x == block[0].x && y == block[0].y){
      return true;
    }
  }
  return false;
}

ソース

#include <iostream>
#include <map>
#include <vector>
using namespace std;

typedef struct Point{
  int x, y;
  bool operator == (const Point p) const{
    return x == p.x && y == p.y;
  }
  bool operator < (const Point p) const{
    return x < p.x || x == p.x && y < p.y;
  }
}Point;

int n, k;
vector<Point> node;
vector<Point> block;
Point goal;
map<vector<Point>, map<int, int> > hash;
int vect[6][2] = {{0, -1}, {1, -1}, {1, 0}, {0, 1}, {-1, 1}, {-1, 0}};

bool isNext(int x1, int y1, int x2, int y2);
bool isHit(int x, int y);
bool isMove(int index, int v);
int solv(int step);
int solv2(int step, int i);

bool isNext(int x1, int y1, int x2, int y2){
  for(int i = 0; i < 6; i++){
    if(x1 - x2 == vect[i][0] && y1 - y2 == vect[i][1]){
      return true;
    }
  }
  return false;
}

bool isHit(int x, int y){
  for(int i = 0; i < node.size(); i++){
    if(x == node[i].x && y == node[i].y){
      return true;
    }
  }
  for(int i = 0; i < block.size(); i++){
    if(x == block[i].x && y == block[i].y){
      return true;
    }
  }
  return false;
}

bool isMove(int index, int v){
  Point np = {node[index].x + vect[v][0], node[index].y + vect[v][1]};

  if(isHit(np.x, np.y)){
    return false;
  }

  //after node
  if(index != 0){
    if(!isNext(np.x, np.y, node[index - 1].x, node[index - 1].y)){
      return false;
    }
  }
  //before node
  if(index != node.size() - 1){
    if(!isNext(np.x, np.y, node[index + 1].x, node[index + 1].y)){
      return false;
    }
  }

  return true;
}

bool checkNode(){
  for(int i = 0; i < node.size() - 1; i++){
    for(int j = i + 2; j < node.size(); j++){
      if(isNext(node[i].x, node[i].y, node[j].x, node[j].y))return false;
    }
  }

  return true;
}

int solv(int step){
  if(step >= 20)return 20;
  if(node[0] == goal)return step;

  int c = hash[node][step];
  if(c > 0)return c;

  int s = solv2(step, 0);
  hash[node][step] = s;

  return s;
}

int solv2(int step, int i){
  if(i >= node.size()){
    if(checkNode())return solv(step + 1);
    return 20;
  }

  //no move
  int min = solv2(step, i + 1);
  //move
  for(int j = 0; j < 6; j++){
    //node move check
    if(isMove(i, j)){
      node[i].x += vect[j][0];
      node[i].y += vect[j][1];
      int s = solv2(step, i + 2);//move next next node
      if(min > s)min = s;
      node[i].x -= vect[j][0];
      node[i].y -= vect[j][1];
    }
  }

  return min;
}

int main(){
  while(cin >> n, (n)){
    node.clear();
    for(int i = 0; i < n; i++){
      Point tmp;
      cin >> tmp.x >> tmp.y;
      node.push_back(tmp);
    }

    cin >> k;
    block.clear();
    for(int i = 0; i < k; i++){
      Point tmp;
      cin >> tmp.x >> tmp.y;
      block.push_back(tmp);
    }

    hash.clear();
    cin >> goal.x >> goal.y;

    cout << solv(0) << endl;
  }

  return 0;
}

参考

2006年ICPC公式HP