欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

做题总结——Pawn’s Revenge

程序员文章站 2024-02-29 10:32:58
...

做题总结——Pawn’s Revenge


题目描述
做题总结——Pawn’s Revenge

这道题目自己一开始时也没有思路(后来才发现其实也并不难,实在是学的不太好),后来从网上查找了一些资料,大概明白了这道题目的思路。这道题目是在已经有且只有一个K棋子的情况下,通过增加最少数量的的pawn棋子,能够将对方的所有的*棋子全部攻击到,其中K能够攻击其余八个方向,pawn棋子只能攻击左上角以及右上角两个方向。

其实这道题目直接利用暴力枚举法进行解决。

首先,对所有的棋子构建一个标记数组,判断已有K棋的其余八个方向是否含有星棋,有的话则将那个星棋标记已访问(这里需要注意边界条件)。

然后,开始从第一行第一列的棋子进行遍历,如果该棋子是星棋并且未被访问,则先判断右下角的棋子是否是空,如果为空则可以放pawn棋子,将该星棋标记为已访问,同时放下的pawn棋子的右上角的棋子无论是否是星棋,都将其标记为已访问。如果右下角无法放pawn棋,再判断左下角是否可以放下pawn棋,如若可以则将星棋标记为已访问(这里不需要再将放置的pawn棋的左上角的棋标记已访问,因为左上角的棋一定比右上角的棋先进行遍历判断)。在这整个判断的剁成中,一定要注意边界条件的限制(一般来说这种有行有列、二维数组的题目都需要注意边界条件的限制),这一重点一定需要在代码中体现出来,否则代码也不会正确。

上面中为什么先判断右下角是否鞥放置星棋而不是左下角呢?个人感觉是因为遍历判断的时候是从做向右判断的…

最后,再将整个棋盘遍历一遍,查看是否还有星棋。如果有的话则说明无法将对方的星棋全部攻击,输出-1;如果没有的话输出需要放置的星棋数量。

整个题目的接替思路大概就是如此,想到其实也不太容易(自己是这么觉得的,还是因为水平不够啊…),还有就是在代码实现的时候,其实有许多需要注意的小细节一定要到位,细节决定成败啊!

代码实现(C++)

#include <bits/stdc++.h>
using namespace std;
int vis[1020][1020];
int main()
{
    int n, c= 0, i, j;
    char a[1020][1020];
    cin >> n;
    for (i = 0; i < n; i++)
    {
        scanf("%s",a[i]);
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (a[i][j] == 'K')
            {
                for (int k = -1; k <= 1; k++)
                {
                    for (int m = -1; m <= 1; m++)
                    {
                        if (i + k >= 0 && i + k < n && j + m >= 0 && j + m < n && a[i + k][j + m] == '*')
                        {
                            vis[i + k][j + m] = 1;
                        }
                    }
                }
            }
        }
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (a[i][j] == '*' && !vis[i][j])
            {
                if (i + 1 < n && j + 1 < n && a[i + 1][j + 1] == '-')
                {
                    a[i + 1][j + 1] = 'p';
                    vis[i][j] = 1;
                    c++;
                    if (j + 2 < n)
                    {
                        vis[i][j + 2] = 1;
                    }
                }
                else if (i + 1 < n && j - 1 >= 0 && a[i + 1][j - 1] == '-')
                {
                    a[i + 1][j - 1] = 'p';
                    vis[i][j] = 1;
                    c++;
                }
            }
        }
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (a[i][j] == '*' && !vis[i][j])
            {
                cout << "-1" << endl;
                return 0;
            }
        }
    }
    cout << c << endl;
    return 0;
}

这个是暑假的第一篇做题总结,自己的学习还是有些松懈,时间安排不够合理,今后必定要多做题、多总结,朝着算法的方向前进,加油!!!