题解：P12658 [KOI 2023 Round 1] 格子游戏

· · 题解

题意简述

两名玩家在 N 行 M 列的棋盘上轮流移动棋子。棋子每次可以：

  1. 向下移动一格。
  2. 向右移动一格。
  3. 沿右下对角线移动 1 到 K 格（K=0 时禁用此操作）。

不能移动到封锁格子或超出棋盘边界。游戏目标是将棋子移动到右下角 (N,M)，最后移动者获胜。给定 Q 个初始位置，需要判断每个位置下先手是否能必胜。

关键点：

输出要求：

对于每个查询位置，输出“First”（先手胜）或“Second”（后手胜）。

思路

这是一个典型的博弈论问题，我们可以用动态规划解决此问题。 \\ 既然是动态规划，那三要素可不能少。

状态

我们定义一个布尔类型的 dp 数组，dp_{i,j} 表示到达了这个点是必胜点还是必败点。到时候需要询问的时候查询一下 dp 数组就行了。 \\ 必胜点的定义：如果从必胜点开始走，怎么走都会输，也就是走到的都是必败点，那么称这个点为必胜点，反之则为必败点。

边界

边界其实很容易确定，很明显，如果都到达终点了，那游戏肯定赢了呀。所以初始化 dp_{n,m} 为必胜点。

转移

终于到达了设计动态规划中最难的一环，但由于这题出的比较简单，这里转移还是很好想到的。这里题目已经说的很清楚了，不难想到，dp_{i,j} 可以由 dp_{i+1,j} 和 dp_{i,j+1}，还有 dp_{i+1,j+1},dp_{i+2,j+2},\dots,dp_{i+k,j+k} 转移而来。他们之中只要由一个值为真，也就是必胜点，那么 dp_{i,j} 就为假。为什么我会这么说，因为如果此时的一方走到了这个点，那么另一方就一定可以走到一个必胜点，那么这个点就是一个必败点。

\\

具体步骤看代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=305;
char a[maxn][maxn];
bool dp[maxn][maxn];
int n,m,k,q;
int main()
{
    cin>>n>>m>>k;
    dp[n][m]=true;//初始化
    for(int i=1;i<=n;i++) scanf("%s",a[i]+1);//读入从(1,1)开始的字符矩阵
    for(int j=m;j;j--)
    for(int i=n;i;i--)//倒着枚举，因为边界点在(n,m)
     {
        if(a[i][j]=='#') continue;//如果是封锁点，跳过。
        bool res=false;
        res|=dp[i+1][j];res|=dp[i][j+1];
        for(int l=1;l<=k;l++)//枚举k
         {
            if(i+l>n||j+l>m) break;//越界了，则终止
            res|=dp[i+l][j+l];
         }
        dp[i][j]=!res;//一定要取反
     }
    cin>>q;
    while(q--)
     {
        int x,y;
        cin>>x>>y;
        if(dp[x][y]) cout<<"Second";
        else cout<<"First";
      /*这里需要重点讲一下，如果这个点是必胜点，那么根据状态的定义，
        从必胜点开始走，走到的所有点都是必败点。所以如果先手先走，那
        么怎么走都是必败点，所以后手有必胜策略。反之则是先手有必胜策略。*/
        cout<<"\n";
     }
    return 0;
}