Catalog
洛谷P1002过河卒

#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int MX[] = {0,-1,-2,-2,-1,1,2,2,1};//记录马能到达的位置
const int MY[] = {0,-2,-1,1,2,2,1,-1,-2};
ull destination[30][30];
int book[30][30];
int main(){
int dx,dy,mx,my;
cin >> dx >> dy >> mx >> my;
++dx;++dy;++mx;++my;//防止数组越界全部加1
destination[1][1] = 1;//初始化马的初始位置
book[mx][my] = 1;//记录马能到达的位置的值为1
for(int i = 1; i <= 8;i++)
book[mx + MX[i]][my + MY[i]] = 1;//作记录
for(int i = 1;i <= dx;i++)
for(int j = 1;j <= dy;j++){
if(book[i][j]) continue;
destination[i][j] = max(destination[i][j],destination[i-1][j]+destination[i][j-1]);//状态转移方程
}
cout << destination[dx][dy];
}
Author: superzhaoyang
Link: http://yoursite.com/2019/09/21/洛谷P1002过河卒/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝

Comment