P3930 SAC E#1 - 一道大水题 Knight

    • 111通过
    • 1.4K提交
  • 题目提供者 ProjectWTA
  • 评测方式 云端评测
  • 标签 广度优先搜索,BFS 状态压缩,状压 进制 洛谷原创 O2优化 高性能
  • 难度 提高+/省选-
  • 时空限制 3000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    毒奶色和F91是好朋友。

    题目描述

    他们经常在一起玩一个游戏,不,不是星际争霸,是国际象棋。

    毒奶色觉得F91是一只鸡。他在一个n×n的棋盘上用黑色的城堡(车)、骑士(马)、主教(象)、皇后(副)、国王(帅)、士兵(卒)摆了一个阵。

    然而F91觉得毒奶色是一只鸡。他发起了挑战:他要操纵一个白色骑士,不经过任何一个棋子的攻击范围(F91可以连续行动,而毒奶色的棋子不会动,除非白骑士进入了对方的攻击范围),并击杀毒奶色的国王(即进入黑国王所在的位置)。

    请告诉F91他最少需要多少步骤来完成这一项壮举。

    注意:

    1.当F91的白骑士走到毒奶色的棋子所在的格子上的时候,会击杀(吃掉)该棋子。这个棋子也就不再对F91的白骑士有威胁了。

    2.如果白骑士开场就在黑子的攻击范围内,则立刻被击杀、F91立刻失败。

    3.即使白骑士在攻击王的瞬间进入了其他棋子攻击范围(即其他棋子“看护”着王所在的格子),依然算F91获胜。

    攻击范围:

    城堡:横、竖方向所有位置,直到被一个其他棋子阻拦。

    ..#..
    ..#..
    ##C##
    ..#..
    ..#..

    骑士:横2竖1或者横1竖2的所有位置(最多8个,类似日字)。

    .#.#.
    #...#
    ..K..
    #...#
    .#.#.

    主教:斜向(45°)所有位置,直到被一个其他棋子阻拦。

    #...#
    .#.#.
    ..B..
    .#.#.
    #...#

    皇后:城堡和主教的结合体(既能横/竖向攻击,也能45°角斜向攻击,直到被其他棋子阻挡)。

    #.#.#
    .###.
    ##Q##
    .###.
    #.#.#

    国王:身边8连通位置的8个格子。

    .....
    .###.
    .#X#.
    .###.
    .....

    士兵:左下方/右下方(45°)的格子(最多2个)。

    .....
    .....
    ..P..
    .#.#.
    .....

    其中字母表示棋子类型,参考输入格式。

    ‘#’表示可攻击范围。

    输入输出格式

    输入格式:

    输入包含多组数据。

    每一组数据中,第一行一个整数n表示棋盘规模。

    接下来n行,每行一个长度为n的字符串。描述棋盘的格局。

    其中:

    .表示空

    O表示白骑士

    C表示黑城堡

    K表示黑骑士

    B表示黑主教

    Q表示黒皇后

    X表示黑国王

    P表示黑士兵

    输出格式:

    对于每一个测试数据,每行输出一个整数,表示F91的最小步数。

    如果无论F91如何行动也无法击杀黑国王,输出-1。

    输入输出样例

    输入样例#1: 复制
    8
    ...X....
    ........
    ........
    ........
    ........
    ........
    ........
    ......O.
    输出样例#1: 复制
    4
    输入样例#2: 复制
    8
    ......X.
    ........
    .O......
    ...P.Q.C
    .....B..
    ........
    ...K....
    ........
    输出样例#2: 复制
    7

    说明

    输入最多包含5组数据。

    对于20%的数据,毒奶色只有国王。n <= 8。

    对于30%的数据,毒奶色只有国王、骑士。n <= 8。

    对于60%的数据,毒奶色只有国王、骑士、王后。n <= 50。

    对于100%的数据,毒奶色可以有全套16颗棋子(2城堡,2骑士,2主教,1后,1王,8兵)。n <= 50。

    温馨提示:

    时间限制可能比想象之中还要更紧一点,请注意实现细节以保证性能。

    样例2解释:

    一种可行的做法是:

    ......X.
    .3..6...
    .O5.....
    4.2P.Q.C
    1....B..
    ........
    ...K....
    ........

    标程展开

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。