「CPP-assign-2009-10-27」の編集履歴（バックアップ）一覧はこちら

「CPP-assign-2009-10-27」(2009/10/27 (火) 10:10:54) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*A*アルゴリズム
**ソース
#codehighlight(c++){{
#include <iostream>
#include <vector>
#include <queue>

inline int abs(const int x)
{
  return (x >= 0) ? x : -x;
}

struct Point
{
  int x,y;
  Point(){};
  Point(int x, int y)
    : x(x), y(y)
  {
  };
};

class EightPazzle
{
private:
  int path;
  std::vector<std::vector<int> > number;
public:
  EightPazzle(const EightPazzle &obj);
  EightPazzle(std::vector<std::vector<int> > array);
  int cost_to_goal() const;
  const int get_path() const{return path;};
  int cost() const{ return cost_to_goal() + path; };
  Point zero() const
  {
    for(unsigned int i=0; i<number.size(); ++i)
      for(unsigned int j=0; j<number[i].size();++j)
	if(number[i][j] == 0)
	  return Point(i, j);
    return Point(-1,-1);
  };
  void older_age(){++path;};
  void restore_age(){--path;};
  void next(std::priority_queue<EightPazzle>& task);
  friend std::ostream &operator<<(std::ostream &st, const EightPazzle& obj)
  {
    for(std::vector<std::vector<int> >::const_iterator i = obj.number.begin();
	i != obj.number.end(); ++i)
      {
	for(std::vector<int>::const_iterator j = i->begin();
	    j != i->end(); ++j)
	  st << *j;
	st << std::endl;
      }
    return st;
  };
  friend bool operator<(const EightPazzle &a, const EightPazzle &b)
  {
    return a.cost() > b.cost();
  };
};

EightPazzle::EightPazzle(const EightPazzle &obj)
  : path(obj.path), number(obj.number)
{  
};

EightPazzle::EightPazzle(std::vector<std::vector<int> > array)
  : path(0)
{
  number = array;
};

int EightPazzle::cost_to_goal() const
{
  int distance = 0;
  for(unsigned int i=0; i<number.size(); ++i)
    for(unsigned int j=0; j<number[i].size(); ++j)
      if(number[i][j] == 0)
	distance += (number.size() - i - 1) + (number.size() - j - 1);
      else
	distance += abs( (number[i][j] - 1)/3 - i)
	  +abs( (number[i][j] - 1)%3 - j);
  return distance;
}

void EightPazzle::next(std::priority_queue<EightPazzle>& task)
{
  typedef std::vector<int>::iterator itr;
  std::vector<int> vx, vy;
  Point z = this->zero();
  if(z.x != 0) vx.push_back(-1);
  if(z.y != 0) vy.push_back(-1);
  if(z.x != number.size() - 1) vx.push_back(1);
  if(z.y != number.size() - 1) vy.push_back(1);

  for(itr i = vx.begin(); i != vx.end(); ++i)
    {
      std::swap(number[z.x][z.y], number[z.x + *i][z.y]);older_age();
      task.push(*this);
      std::swap(number[z.x][z.y], number[z.x + *i][z.y]);restore_age();
    }
  for(itr i = vy.begin(); i != vy.end(); ++i)
    {
      std::swap(number[z.x][z.y], number[z.x][z.y + *i]);older_age();
      task.push(*this);
      std::swap(number[z.x][z.y], number[z.x][z.y + *i]);restore_age();
    }
}

int main()
{
  std::vector<std::vector<int> > init_array;
  int temp[3][3] = {{1, 3, 5}, {7, 0, 2},{8, 4, 6}};
  for(int i=0; i<3; ++i)
    init_array.push_back(std::vector<int>(temp[i], temp[i]+3));
  EightPazzle start(init_array);
  std::cout << "start\npath:" << start.get_path()
	    << ",cost:" << start.cost_to_goal() << "\n" << start;

  std::priority_queue<EightPazzle> task;
  task.push(start);
  int i=0;
  while(task.top().cost_to_goal() != 0)
    {
      EightPazzle working(task.top());
      task.pop();
      std::cout << i << "------------\npath:" << working.get_path()
		<< ",cost:" << working.cost_to_goal() << "\n"
		<< working;

      working.next(task);
      ++i;
    }

  std::cout << "-----END-----\npath:" << task.top().get_path() << "\n"
	    << task.top();
}
}}