c# - 删除最少数量的国际象棋骑士,这样剩余的骑士就不会威胁另一个骑士
问题描述
我很难想出骑士游戏任务的算法。
任务描述如下:
骑士游戏是在一个尺寸为 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
解决方案
该算法存在缺陷,在这个较小的板上可以更容易地看到:
4
000K
0K00
00K0
K000
这里的解应该是2;但算法返回 3。原因是该算法移除了攻击次数最多的第一个骑士;假设这个删除是正确答案的一部分;但是,可能有多个骑士具有这样的攻击次数,第一个不一定是最佳选择。
即使您在循环内添加,也knights.OrderByDescending(k => k.KnightAttacks.Count())
不会做您希望它做的事情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();
}
推荐阅读
- python - python3 是否有等效的 R DT 包?
- excel - 在没有小数 VBA 的单元格中插入一个值
- python - 带有色调参数的seaborn散点图中的ValueError
- php - 是否可以在 CodeIgniter 4 的路由中使用动态控制器名称?
- java - 模拟对象未返回预期值
- php - Laravel Composer 错误:安装失败,将 ./composer.json 还原为其原始内容
- javascript - Sequelize:A未关联到B“nodejs
- awk - 如何在带有逗号文本字段的大型 csv 中使用 awk 分隔符
- r - R 包 googlesheets4 返回客户端错误:(429) RESOURCE_EXHAUSTED 读取公共工作表时
- php - Cakephp 4:FIND_IN_SET 不返回结果