洛谷趣题【过河卒】参考题解

本文主要是介绍洛谷趣题【过河卒】参考题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

背景

今天逛洛谷才注意到这道题，原题连接【P1002 [NOIP2002 普及组] 过河卒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)】

对于爱下棋的我来说，当然是必刷之题。

题意

小卒起始点在左上角(0,0)处，我们的程序将接收两个坐标：小卒目标点右下角(end_x,end_y)、以及敌方馬的坐标点(horse_x,horse_y)。

其中，小卒只可以往右或者往下走一格，并且不能经过馬脚和馬位，最多九个点不能经过。

求从左上角到右下角一共有多少种方案。数据量约定坐标最大值不超过20。

解析

乍一看，我们都知道这个应该就是一个递推算法的考察题，其中目标点的方案数求解公式应该是

res(end_x,end_y)=res(end_x-1,end_y)+res(end_x,end_y-1)

其中res(0,0)=1

我们从(0,0)出发，使用队列这个先进先出的数据结构可以有效解决这个问题。

由于一个点可能由于两个点到达，为了去重，我们需要使用一个标记数组flag和双队列，使得每个点只会入队最多一次。

考虑到有敌方馬的存在，我们给馬脚和馬位打上负值，每次经过这些负值位置则不入队，否则入队并标记这个位置，下次再搜索到这个位置时，只增加方案数，并不继续入队。

到队列全空时，结果就出来了，正是res(end_x,end_y)

时间复杂度O(n^2)，空间复杂度O(n^2)

代码

#include<bits/stdc++.h>
using namespace std;class point {public:int x,y;
};int main() {int start_x=0,start_y=0;int horse_x,horse_y;int end_x,end_y;cin>>end_x>>end_y>>horse_x>>horse_y;long long res[21][21]= {0};res[0][0]=1;bool flag[21][21]= {0};int horse_direct[][2]= {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};res[horse_x][horse_y]=-1;for(int k=0; k<8; k++) {int x=horse_x+horse_direct[k][0];int y=horse_y+horse_direct[k][1];if(x>=0&&y>=0&&x<=end_x&&y<=end_y) {res[x][y]=-1;}}int soldier_direct[][2]= {{0,1},{1,0}};queue<point> q;q.push({start_x,start_y});while(!q.empty()) {queue<point> nq;memset(flag,0,sizeof(flag));while(!q.empty()) {point p=q.front();q.pop();for(int k=0; k<2; k++) {int x=p.x+soldier_direct[k][0];int y=p.y+soldier_direct[k][1];if(x<0||y<0||x>end_x||y>end_y) {continue;}if(res[x][y]<0) {continue;}res[x][y]+=res[p.x][p.y];if(!flag[x][y]) {nq.push({x,y});flag[x][y]=1;}}}q=nq;}cout<<res[end_x][end_y]<<endl;return 0;
}