做题总结——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;
}

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