おねえさんの問題を解いてみる

超高速グラフ列挙アルゴリズム?〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ?

作者: ERATO 湊離散構造処理系プロジェクト,湊真一
出版社/メーカー: 森北出版
発売日: 2015/04/08
メディア: 単行本（ソフトカバー）
この商品を含むブログ (3件) を見る

www.youtube.com

せっかく買ったので、夜を徹する覚悟で読み始めたのだが、いきなり詰まった。プログラムを書いてみようと思って、C++でいじいじしていたらもう朝になりかけている...実装能力無いなあ。。。

#include <iostream>
#include <list>
#include <vector>
#include <utility>
#include <stdlib.h>
#include <sys/time.h>

typedef std::pair<int, int> cood_pair;

bool find (int x, int y, std::vector<cood_pair *> *visited);
int combination (int size, int x, int y, std::vector<cood_pair *> *visited);
std::vector<cood_pair *>* copy_vector (std::vector<cood_pair *> vector);


double get_dtime(void){
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return ((double)(tv.tv_sec) + (double)(tv.tv_usec) * 0.001 * 0.001);
}


int main (int argc, char *argv[])
{
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " size\n";
        exit (EXIT_FAILURE);
    }
    int size = atol (argv[1]);

    std::vector<cood_pair *> *visited = new std::vector<cood_pair *>;

    double d0, d1;
    d0 = get_dtime ();
    int ret = combination (size, 0, 0, visited);
    d1 = get_dtime ();
    std::cout << "Elapsed = " << (d1 - d0) << "\n";

    // std::cout << "Ret = " << ret << "\n";
}


bool find (int x, int y, std::vector<cood_pair *> *visited)
{
    std::vector<cood_pair *>::iterator it = visited->begin();
    while (it != visited->end()) {
        if ((*it)->first == x && (*it)->second == y) {
            return true;
        }
        it++;
    }
    return false;
}


std::vector<cood_pair *>* copy_vector (std::vector<cood_pair *> *vector)
{
    std::vector<cood_pair *> *copy_visited = new std::vector<cood_pair *>;
    std::copy(vector->begin(), vector->end(), back_inserter(*copy_visited));
    return copy_visited;
}


int combination (int size, int x, int y, std::vector<cood_pair *> *visited)
{
    if (x < 0 || y < 0) {
        return 0;
    } else if (x >= size || y >= size) {
        return 0;
    } else if (x == (size-1) && y == (size-1)) {
        return 1;
    }

    if (find (x, y, visited)) {
        return 0;
    }

    cood_pair *new_xy = new cood_pair(x, y);
    visited->push_back (new_xy);

    int count = 0;

    std::vector<cood_pair *> *copy_visited;

    copy_visited = copy_vector (visited);
    count += combination (size, x    , y - 1, copy_visited);
    delete copy_visited;

    copy_visited = copy_vector (visited);
    count += combination (size, x - 1, y    , copy_visited);
    delete copy_visited;

    copy_visited = copy_vector (visited);
    count += combination (size, x + 1, y    , copy_visited);
    delete copy_visited;

    copy_visited = copy_vector (visited);
    count += combination (size, x    , y + 1, copy_visited);
    delete copy_visited;

    return count;
}