c# - 删除最少数量的国际象棋骑士，这样剩下的骑士就不会威胁到另一个骑士

Question

我无法为 Knight Game 任务想出一个算法。

任务的描述是:

骑士游戏是在一个尺寸为 N x N 的棋盘上进行的，棋盘上有很多 0 <= K <= N² 的国际象棋骑士。

我收到一个棋盘(字符矩阵)，其中“K”表示骑士，“0”表示空单元格。我的任务是移除最少的骑士，这样就不会剩下可以攻击另一个骑士的骑士了。在第一行，我收到了板的 N 尺寸。在接下来的 N 行中，我收到包含 Ks 和 0s 的字符串。

到目前为止，这是我设计的:

public class SolutionTwo
{
    public static void Main()
    {
        var size = int.Parse(Console.ReadLine());

        var board = new char[size][];
        PrepareBoard(board);

        var knights = new List<Knight>();

        for (int x = 0; x < board.Length; x++)
        {
            for (int y = 0; y < board[x].Length; y++)
            {
                if (board[x][y] == 'K')
                {
                    knights.Add(new Knight()
                    {
                        X = x,
                        Y = y,
                        KnightAttacks = GetKnightAttacks(x, y, board)
                    });
                }
            }
        }

        var count = 0;

        foreach (var knight in knights.OrderByDescending(k => k.KnightAttacks.Count()))
        {
            if (!IsReaminingHits(board))
            {
                break;
            }

            board[knight.X][knight.Y] = '0';
            count++;

            foreach (var subK in knight.KnightAttacks)
            {
                var c = knights.Single(k => k.X == subK.Item1 && k.Y == subK.Item2);

                c.KnightAttacks.Remove(new Tuple<int, int>(knight.X, knight.Y));
            }

            // for test purposes
            //Console.WriteLine($"Kn: [{knight.X} {knight.Y}] - he attacks: {string.Join(" ", knight.KnightAttacks)} {knight.KnightAttacks.Count()}");
        }

        Console.WriteLine(count);
    }

    private static bool IsReaminingHits(char[][] board)
    {
        for (int i = 0; i < board.Length; i++)
        {
            for (int j = 0; j < board[i].Length; j++)
            {
                if (board[i][j] == 'K')
                {
                    if (GetKnightAttacks(i, j, board).Count > 0)
                    {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    private static void PrepareBoard(char[][] board)
    {
        for (int i = 0; i < board.Length; i++)
        {
            board[i] = Console.ReadLine()
                .ToCharArray();
        }
    }

    private static List<Tuple<int, int>> GetKnightAttacks(int x, int y, char[][] board)
    {
        var deltas = new int[8][]
        {
            new int[] {-2, -1},
            new int[] {-2, +1},
            new int[] {+2, -1},
            new int[] {+2, +1},
            new int[] {-1, -2},
            new int[] {-1, +2},
            new int[] {+1, -2},
            new int[] {+1, +2}
        };

        var xCandidate = 0;
        var yCandidate = 0;

        var list = new List<Tuple<int, int>>();

        for (int i = 0; i < 8; i++)
        {
            xCandidate = x + deltas[i][0];
            yCandidate = y + deltas[i][1];

            if (0 <= xCandidate && xCandidate < board.Length
                && 0 <= yCandidate && yCandidate < board[0].Length
                && board[xCandidate][yCandidate] == 'K')
            {
                list.Add(new Tuple<int, int>(xCandidate, yCandidate));
            }
        }

        return list;
    }
}

public class Knight
{
    public int X { get; set; }

    public int Y { get; set; }

    public List<Tuple<int, int>> KnightAttacks { get; set; } = new List<Tuple<int, int>>();
}

---

示例#1:

输入:

5 
0K0K0
K000K
00K00
K000K 
0K0K0

预期结果:1

---

示例#2:

输入:

8
0K0KKK00
0K00KKKK
00K0000K
KKKKKK0K
K0K0000K
KK00000K
00K0K000
000K00KK

预期结果:12

Answer 1

算法有缺陷，在这个较小的板上更容易看出:

4
000K
0K00
00K0
K000

这里的解应该是2；但算法返回 3。这是因为算法移除了攻击次数最多的第一个骑士；假设此删除是正确答案的一部分；但是，具有该攻击次数的骑士可能有多个，第一个不一定是最佳选择。

此外，即使您添加了 knight.KnightAttacks.Clear( ); 在循环内，因为它必须评估所有值才能枚举它们；但当然，随着您开始移除骑士，这些数字会有所不同。

正确的算法将需要尝试具有相同攻击次数的所有备选方案，以找出最佳方案。我还可以想出攻击次数最多的骑士不是最佳选择的场景。例如:

7
K00000K
00K0K00
KK000KK
0K0K0K0
0000000
0000000
0000000

因此，使用以下代码替换以 var count=0; 开头的代码会稍微改进算法(例如，对于我的小示例，它得到正确答案 2，对于“示例 #2”，它得到 12 ");但不是完整的解决方案:

var count = 0;
while (knights.Any(k => k.KnightAttacks.Count > 0))
{
    var knight = knights.OrderByDescending(k => k.KnightAttacks.Count).First();

    // for test purposes
    //Console.WriteLine($"Kn: [{knight.X} {knight.Y}] - he attacks: {string.Join(" ", knight.KnightAttacks)} {knight.KnightAttacks.Count()}");

    board[knight.X][knight.Y] = '0';
    count++;

    foreach (var subK in knight.KnightAttacks)
    {
        var c = knights.Single(k => k.X == subK.Item1 && k.Y == subK.Item2);

        c.KnightAttacks.Remove(new Tuple<int, int>(knight.X, knight.Y));
    }
    knight.KnightAttacks.Clear();
}