专栏首页个人学习总结做题总结——Pawn’s Revenge

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 做题总结——Delayed Work

    这道题目是来计算最低的支付金额,该金额由工人的工资和罚款两部分组成。根据题意描述可知,工资的表达式:MX,罚款的表达式:(KP)/M,因此总金额表达式:MX+(...

    用户8224910
  • 做题总结—— Latin Squares

    题目就是输入一个二维数组(用来表示矩阵),判断对于矩阵中的每一个数字是否在该数字所在的行、所在的列的只出现一次(相当于数独的概念)。如果是的话,则该矩阵是拉丁方...

    用户8224910
  • 做题总结——Fear Factoring

    开始自己的做法是特别愚蠢的 暴力破解法,也就是分别枚举[a,b]区间里每一个数的因数,最后累加起来,可想而知这种做法肯定是不对的。后面听了学长的讲解,这道题一共...

    用户8224910
  • 做题总结——中位数

    这道题目题意其实并不理解,相当于在插入数据的过程中动态求中位数,每当插入奇数个数据时就求这所有奇数个数据的中位数。

    用户8224910
  • 做题总结——造房子

    用户8224910
  • OpenAI算法掌握困难游戏,AI智能体胜过人类玩家

    OpenAI最新论文中,详细介绍了在复古平台游戏Montezuma’s Revenge中AI胜过人类玩家。表现最佳的迭代发现了第一关中24个房间中的22个,偶尔...

    AiTechYun
  • 做题总结——younik要排号

    这道题目理解起来不难,就相当于求younik之前有多少个不同的人,再加上一,就是younik是第几个被叫到的人。

    用户8224910
  • 做题总结——使徒袭来

    这道题目利用数学知识可以知道,当三个正整数的值相等时,三个数的和最小,相当于a=b=c=n^(1/3)时,(a+b+c) min=3*n ^(1/3),编写代码...

    用户8224910
  • 做题总结——虚空之力

    这道题目是求出一个字符串中能够挑选出对应字符从而组成指定字符串(“king” 或 “kinging”)的数量

    用户8224910
  • 做题总结——走出迷宫

    从起点开始,分别向上、下、左、右四个方向进行搜索,如果搜索到了终点,则说明能够到达终点;否则,将该点压入队列之中,继续进行下面的搜索,并将该点标记成已访问。

    用户8224910
  • 挑战程序竞赛系列(46):4.1Polya 计数定理(2)

    思路: 首先能想到的是Polya计数,但是此题的trick在于还需要控制A或B不能连续出现的次数。

    用户1147447
  • 做题总结——数字三角形

    先介绍一种解法。这道题目可以利用“杨辉三角”的思路,根据一个上面的元素与下面两个元素的递推公式(在动态规划里面称作状态转移方程),从下至上地解决此问题(详细思路...

    用户8224910
  • 做题总结——牛牛爱博弈

    自己再网上看了一些题解,感觉还是没有弄明白这其中的原理,所以就不在这写了,关于数论中博弈原理的各种应用需要自己去进行学习,总之 结论就是当n%3==0时,则牛牛...

    用户8224910
  • 做题总结——小M和天平

    根据这道题给出的数据范围可以知道,利用所有的石头能够查询的物体质量是不会查过100*100=10000的,所以可以直接利用暴力枚举的方法进行求解。

    用户8224910
  • 做题总结——单词查找树

    这道题目就是一道Trie树相关操作的题目(这道题目只涉及了插入操作),求最少的结点数目就相当于输出向Trie树中插入的最后一个结点的序号(注意开始就有根结点)

    用户8224910
  • 强化学习简介

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    Steve Wang
  • 做题总结——牛牛爱字符串

    这道题目题意比较好理解,就是输出所给字符串中含有的数字,对于有前导零的数字需要注意去掉前导零,同时注意如果只有一个数字0直接输出。

    用户8224910
  • 7月份刷题总结(水题总结)

    3. 数组过大超过限制,可定义为全局变量。开一个20000大小的数组,用memset函数赋初值。

    天道Vax的时间宝藏
  • 经历的面试题,先做下部分总结。

    纪莫

扫码关注云+社区

领取腾讯云代金券