ACM问题:硬币翻转,帮助我确定问题的类型

Question

我正在为即将到来的ACM编程竞赛练习一周,我对这个编程问题感到困惑.

问题如下:

---

你有一个由大小为4的正方形网格构成的拼图.每个网格方格都有一个硬币; 每个硬币显示头部(H)和尾部(T).这里展示了一个这样的难题:

HHHH
TTTT
HTHT
TTHT

任何当前显示Tails(T)的硬币都可以翻转到Heads(H).但是,每当我们翻转硬币时,我们还必须在相同的行中向上,向下和向左和向右翻转相邻的硬币.因此,如果我们在第二排翻转第二枚硬币,我们还必须翻转另外4枚硬币,给我们这个安排(改变的硬币以粗体显示).

H T HH
H H H T
H H HT
TTHT

如果硬币位于拼图的边缘,那么一边或另一边没有硬币,那么我们就会翻转更少的硬币.我们不会"缠绕"到另一边.例如,如果我们翻转上面的arragnement的右下角硬币,我们会得到:

HTHH
HHHT
HHH H
TT T H.

注意:只能选择显示(T)尾部的硬币进行翻转.然而,无论何时我们翻转这样的硬币,相邻的硬币也会被翻转,无论其状态如何.

这个难题的目标是让所有硬币显示出头部.虽然有些arragnements可能没有解决方案,但所有问题都会有解决方案.我们正在寻找的答案是,对于任何给定的4x4网格硬币,为了使网格完全成为头部,最少的翻转次数是多少.

对于实施例的网格:
HTHH
TTTH
HTHT
HHTT

这个网格的答案是:2翻转.

---

到目前为止我做了什么:

我将我们的网格存储为二维的布尔数组.Heads = true,tails = false.我有一个翻转(int row,int col)方法,它将根据上面的规则翻转相邻的硬币,我有一个isSolved()方法,它将确定拼图是否处于解决状态(所有头).所以我们有了"机制".

我们遇到问题的部分是我们应该如何进行循环,最少进行深度研究？

Answer 1

您的谜题是经典的广度优先搜索候选者.这是因为您正在寻找尽可能少"移动"的解决方案.

如果你知道目标的移动次数,那么这对于深度优先搜索来说是理想的.

那些维基百科文章包含大量有关搜索工作方式的信息,甚至包含多种语言的代码示例.

如果您确定不会耗尽堆栈空间,则搜索可以是递归的.

Answer 2

编辑:我没有注意到你不能使用硬币作为主要动作,除非它显示尾巴.这确实使秩序变得重要.我会在这里留下这个答案,但也要考虑写另一个.

这里没有伪代码,但请想一想:你能想象自己两次掷硬币吗？会有什么影响？

另外,写下一些任意的板(字面意思,写下来).设置一些真实世界的硬币,并选择两个任意的硬币,X和Y.做一个"X翻转",然后是"Y翻转",然后是另一个"X翻转".写下结果.现在将电路板重置为起始版本,然后执行"Y翻转".比较结果,并考虑发生了什么.尝试几次,有时X和Y靠近,有时不靠近.对你的结论充满信心.

这种思路应该引导您找到一种有限的可能解决方案.您可以非常轻松地测试所有这些.

希望这个暗示不是太明显 - 我会密切关注这个问题,看看你是否需要更多的帮助.这是一个很好的谜题.

至于递归:你可以使用递归.就个人而言,我不会在这种情况下.

编辑:实际上,在第二个想法,我可能会使用递归.它可以让生活变得更加简单.

好吧,也许这还不够明显.让我们标记硬币AP,如下所示:

ABCD
EFGH
IJKL
MNOP

翻转F将始终涉及以下硬币改变状态:BEFGJ.

翻转J将始终涉及以下硬币改变状态:FIJKN.

如果你掷硬币两次怎么办？无论发生什么其他翻转,两个翻转都会相互抵消.

换句话说,翻转F然后J与翻转J然后翻转F.然后F翻转F然后再翻动J然后再翻F再与翻转J开始相同.

因此,任何解决方案都不是"翻转A然后F然后J"的路径 - 它是"翻转<这些硬币>;不要翻转<这些硬币>".(遗憾的是,"翻转"这个词既用于翻转的主要硬币,也用于改变特定动作状态的次要硬币,但从不介意 - 希望我的意思很清楚.)

每枚硬币将作为主要动作使用,或者不作为主要动作,0或1.有16个硬币,因此有2 ^ 16种可能性.所以0可能代表"不做任何事情"; 1可能代表"只是A"; 2可能代表"只是B"; 3"A和B"等

测试每个组合.如果(不知何故)有多个解决方案,请计算每个解决方案中的位数以找到最少的数字.

实现提示:"当前状态"也可以表示为16位数.使用特定硬币作为主要移动将始终使用固定数字(对于该硬币)对当前状态进行异或.这使得很容易计算出任何特定动作组合的效果.

好的,这是C#中的解决方案.它显示了它找到的每个解决方案需要多少次移动,但它不会跟踪那些移动的移动,或移动次数最少的移动.这是一个SMOP :)

输入是一个列表,其中的硬币显示尾部开始 - 所以对于问题中的示例,您将使用参数"BEFGJLOP"启动程序.码:

using System;

public class CoinFlip
{
    // All ints could really be ushorts, but ints are easier 
    // to work with
    static readonly int[] MoveTransitions = CalculateMoveTransitions();

    static int[] CalculateMoveTransitions()
    {
        int[] ret = new int[16];
        for (int i=0; i < 16; i++)
        {
            int row = i / 4;
            int col = i % 4;
            ret[i] = PositionToBit(row, col) +
                PositionToBit(row-1, col) +
                PositionToBit(row+1, col) +
                PositionToBit(row, col-1) +
                PositionToBit(row, col+1);
        }
        return ret;
    }

    static int PositionToBit(int row, int col)
    {
        if (row < 0 || row > 3 || col < 0 || col > 3)
        {
            // Makes edge detection easier
            return 0;
        }
        return 1 << (row * 4 + col);
    }

    static void Main(string[] args)
    {
        int initial = 0;
        foreach (char c in args[0])
        {
            initial += 1 << (c-'A');
        }
        Console.WriteLine("Initial = {0}", initial);
        ChangeState(initial, 0, 0);
    }

    static void ChangeState(int current, int nextCoin, int currentFlips)
    {
        // Reached the end. Success?
        if (nextCoin == 16)
        {
            if (current == 0)
            {
                // More work required if we want to display the solution :)
                Console.WriteLine("Found solution with {0} flips", currentFlips);
            }
        }
        else
        {
            // Don't flip this coin
            ChangeState(current, nextCoin+1, currentFlips);
            // Or do...
            ChangeState(current ^ MoveTransitions[nextCoin], nextCoin+1, currentFlips+1);
        }
    }
}