P2923 [USACO08DEC]赢得跳棋Winning Checkers

    • 4通过
    • 77提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 队列 USACO 2008 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    The cows have taken up the game of checkers with a vengeance.

    Unfortunately, despite their unlimited enjoyment of playing, they are terrible at the endgame and want your help.

    Given an NxN (4 <= N <= 500) checkboard, determine the optimal set of moves (i.e., smallest number of moves) to end the game on the next move. Checkers move only on the '+' squares and capture by jumping 'over' an opponent's piece in the traditional way. The piece is removed as soon as it is jumped. See the example below where N=8:

    - + - + - + - +  The K's mark Bessie's kings; the o's represent the 
    + - + - + - + -  opponent's checkers. Bessie always moves next. The 
    - + - K - + - +  Kings jump opponent's checkers successively in any 
    + - + - + - + -  diagonal direction (and removes pieces when jumped). 
    - o - o - + - + 
    + - K - + - + -  For this board, the best solution requires the lower 
    - o - + - + - +  left King to jump successively across all three of the 
    + - K - + - K -  opponents' checkers, thus ending the game (moving K marked as >K<): 
    Original          After move 1       After move 2        After move 3 
    - + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - + 
    + - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + - 
    - + - K - + - +     - + - K - + - +    - + - K - + - +     - + - K - + - + 
    + - + - + - + -     + - + - + - + -    + ->K<- + - + -     + - + - + - + - 
    - o - o - + - +     - o - o - + - +    - + - o - + - +     - + - + - + - + 
    + - K - + - + -    >K<- K - + - + -    + - K - + - + -     + - K ->K<- + - 
    - o - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - + 
    + ->K<- + - K -     + - + - + - K -    + - K - + - K -     + - K - + - K - 
    
    The moves traversed these squares: 
    1 2 3 4 5 6 7 8           R C 
    1 - + - + - + - +    start: 8 3 
    2 + - + - + - + -    move:  6 1 
    3 - + - K - + - +    move:  4 3 
    4 + - * - + - + -    move:  6 5 
    5 - o - o - + - + 
    6 * - K - * - + - 
    7 - o - + - + - + 
    8 + - K - + - K - 

    Write a program to determine the game-ending sequence for an NxN input board if it exists. There is at least a king and at least one opponent piece on the board. The king can jump a piece on every move of the optimal solution.

    POINTS: 330

    奶牛们在疯狂地玩着西洋跳棋,但是非常不幸,不管他们多么享受,他们还是在最后阶段遇 到了可怕的麻烦,他们需要你的帮助.

    有一个N x N(4 < W < 500)跳棋棋盘,请确定最佳的结束比赛步骤.跳棋子仅仅能够在标记 有“ + ”的格子里停留,通过“飞跃”俘获对方的棋子.刚刚跳过的格子将被立即封锁.请看下面 的例子:

    这是一张边长为8的棋盘图.“K”代表贝茜的王;“0”代表对手的棋子.王需要斜着连续的 跳过对的棋子,跳过的格子将会被封锁.对于这个情况,获胜的方案需要最下面、最左边的王 连续的跳过三个对方的棋子(如下图所示),游戏因此结束.

    请写一个程序,给出输入的棋盘的结束游戏步骤(存在时,是唯一的).至少有一个王和一 个对手棋子在棋盘上.

    无解的时候应当输出impossible

    输入输出格式

    输入格式:

    * Line 1: A single integer: N

    * Lines 2..N+1: Line i+1 contains N characters (each one of: '-', '+', 'K', or 'o') that represent row i of a proper checkboard. Line 2 always begins with '-'.

    输出格式:

    * Lines 1..?: If there is no winning sequence of jump, output

    'impossible' on a line by itself. If such a sequence exists, each line contains two space-separated integers that represent successive locations of a king whose moves will win the game. Any such sequence is acceptable.

    输入输出样例

    输入样例#1: 复制
    8 
    -+-+-+-+ 
    +-+-+-+- 
    -+-K-+-+ 
    +-+-+-+- 
    -o-o-+-+ 
    +-K-+-+- 
    -o-+-+-+ 
    +-K-+-K- 
    
    输出样例#1: 复制
    8 3 
    6 1 
    4 3 
    6 5 
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。