区字棋中的最长非0链

一，区字棋

也叫憋死牛棋。

规则：

棋盘一共只有5个点，双方各2个棋子，还有一个空格。

先手必须移动左边的棋子，之后没有限制，2个棋子任意一个移动到空格皆可。

无法移动者判负。

二，不败策略

因为失败的阵型是固定的，要么2个都在上面，要么2个都在下面，只有这样才有可能被堵住。

所以不败策略也很简单，任意状态下，轮到任意方行动时，都至少有1种行动方法，不会走到固定的失败阵型，这就是不败策略了。

三，有向有环图分析

1，最长非零链

用博弈论分析，这个属于有向有环图游戏，上面的不败策略其实就是说，该有向图的等价图中，最长的非零链的长度为1

我们来验证一下。

（1）给所有状态编号

假设蓝色棋子分别在i,j，空格在k，那么我们编号为i*25+j*5+k，其中0<=i,j,k<=5

所有状态的编号都在0到124之间，但其中有小部分是非法状态（ijk重复），合法状态只有60种。

考虑到2个棋子相同的话，实际上只有30个不同的合法状态。

（2）构建有向图

int getId(int i, int j, int k) {
    return i * 25 + j * 5 + k;
}
vector<int> getIjk(int id) {
    return vector<int>{id / 25, id % 25 / 5, id % 5};
}
vector<int> getNext(int id) {
    auto v = getIjk(id);

}
map<int, vector<int>> bfs(int id)
{
    queue<int>q;
    map<int, int>visit;
    q.push(id);
    visit[id] = 1;
    while (!q.empty()) {
        int t = q.front();
        q.pop();

    }
}