オフラインリアルタイムどう書く第四回の参考問題 解答(C++)

お題はこちらです http://qiita.com/items/9c514267214d3917edf2 。

最初のうちは、枝刈り（絶対にゴールにたどり着けないルートに入ったら先を探索しない）をしようと考えていたんですが、まずは回答出すのが先かなと思い直して総当たりで解いています。
周囲にあるノードと内部にあるノードを区別するのが面倒だったので番兵を使ってすべて内部のノードとして扱っています。
通行止めは２つのノードをもとにユニークな数値を作り`std::set<int>`に格納しています。

一応C++ですが、あんまいりC++らしいコードにはなってませんです。

```cpp:
#include <iostream>
#include <sstream>
#include <string>
#include <set>

const int SIZE       = 5;
const int nodes_SIZE = SIZE + 2;

class Edges
{
public:
    Edges(const std::string& blocked)
    {
        std::stringstream ss(blocked);
        std::string       s;
        while(ss >> s)
        {
            blockedEdges_.insert((s[0] - 'a') * SIZE * SIZE + (s[1] - 'a'));
            blockedEdges_.insert((s[1] - 'a') * SIZE * SIZE + (s[0] - 'a'));
        }
    }
    
    bool isBrocked(int x1, int y1, int x2, int y2) const
    {
        int p1 = ((y1 - 1) * SIZE) + (x1 - 1);
        int p2 = ((y2 - 1) * SIZE) + (x2 - 1);
        
        return blockedEdges_.find(p1 * SIZE * SIZE + p2) != blockedEdges_.end();
    }
    
private:
    std::set<int> blockedEdges_;
};

bool isGoal(int x, int y)
{
    return (x == SIZE) && (y == SIZE);
}

int countRoute(bool nodes[nodes_SIZE][nodes_SIZE], int x, int y, const Edges& edges)
{
    if(isGoal(x, y))
    {
        return 1;
    }
    
    int result = 0;
    nodes[x][y] = true;
    if(( ! nodes[x - 1][y]) && ( ! edges.isBrocked(x, y, x - 1, y))) { result += countRoute(nodes, x - 1, y, edges); }
    if(( ! nodes[x + 1][y]) && ( ! edges.isBrocked(x, y, x + 1, y))) { result += countRoute(nodes, x + 1, y, edges); }
    if(( ! nodes[x][y - 1]) && ( ! edges.isBrocked(x, y, x, y - 1))) { result += countRoute(nodes, x, y - 1, edges); }
    if(( ! nodes[x][y + 1]) && ( ! edges.isBrocked(x, y, x, y + 1))) { result += countRoute(nodes, x, y + 1, edges); }
    nodes[x][y] = false;
    return result;
}

int fukashigi(const std::string& blocked)
{
    bool nodes[nodes_SIZE][nodes_SIZE];
    for(int x = 0; x < nodes_SIZE; ++x)
    {
        for(int y = 0; y < nodes_SIZE; ++y)
        {
            nodes[x][y] = ((x == 0) || (y == 0) || (x == nodes_SIZE - 1) || (y == nodes_SIZE - 1));
        }
    }
    
    Edges edges(blocked);
    
    return countRoute(nodes, 1, 1, edges);
}
```

テスト。Google Testを使っています。

```cpp:
#include <string>
#include <gtest/gtest.h>

int fukashigi(const std::string& blocked);

TEST(FukashigiTest, test)
{
    ASSERT_EQ(fukashigi(""),                                 8512);
    ASSERT_EQ(fukashigi("af"),                               4256);
    ASSERT_EQ(fukashigi("xy"),                               4256);
    ASSERT_EQ(fukashigi("pq qr rs st di in ns sx"),           184);
    ASSERT_EQ(fukashigi("af pq qr rs st di in ns sx"),         92);
    ASSERT_EQ(fukashigi("bg ch di ij no st"),                 185);
    ASSERT_EQ(fukashigi("bc af ch di no kp mr ns ot pu rs"),   16);
    ASSERT_EQ(fukashigi("ab af"),                               0);
    ASSERT_EQ(fukashigi("ty xy"),                               0);
    ASSERT_EQ(fukashigi("bg ch ej gh lm lq mr ot rs sx"),      11);
    ASSERT_EQ(fukashigi("ty ch hi mn kp mr rs sx"),            18);
    ASSERT_EQ(fukashigi("xy ch hi mn kp mr rs sx"),            32);
    ASSERT_EQ(fukashigi("ch hi mn kp mr rs sx"),               50);
    ASSERT_EQ(fukashigi("ab cd uv wx"),                       621);
    ASSERT_EQ(fukashigi("gh mn st lq qr"),                    685);
    ASSERT_EQ(fukashigi("fg gl lm mr rs"),                    171);
}
```