鏈接: 原題鏈接
題目描述
棋盤上 A 點有一個過河卒，需要走到目標 B 點，卒行走的規則：可以向下、或者向右，同時在棋盤上 C 點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，因此稱之為“馬攔過河卒”，
棋盤用坐標表示，A 點 (0, 0)、B 點 (n, m)，同樣馬的位置坐標是需要給出的，
現在要求你計算出卒從 A 點能夠到達 B 點的路徑的條數，假設馬的位置是固定不動的，并不是卒走一步馬走一步，
輸入格式
一行四個正整數，分別表示 B 點坐標和馬的坐標，
輸出格式
一個整數，表示所有的路徑條數，
輸入輸出樣例
輸入 #1
6 6 3 3
輸出 #1
6
說明/提示
對于100%的資料,
1 <= n , m <= 20,
1 ≤ n , m ≤ 20,
0 ≤ 馬的坐標 ≤ 20，
【題目來源】
NOIP 2002 普及組第四題
思路講解
這是一個經典的入門動規題，一開始做這題直接聯想到的是“走迷宮”，于是用DFS去做了，結果未AC，只有40分，有兩個RE，一個TLE，
回過頭來仔細審題：卒只能向下或向右走，那么每個位置只能由這個位置的左邊或上面一個位置達到，滿足最優子結構問題條件，用動規可以解決，
我們定義一個ｆ陣列，f [ i ] [ j ]表示達到( i , j )這個位置的方案數，如果終點坐標為( n , m )則答案即為f [ n ] [ m ]，
關鍵是找遞推式，其實很簡單，因為那么每個位置只能由這個位置的左邊或上面一個位置達到，所以一般的f [ i ] [ j ]=f [ i -1] [ j ] + f [ i ] [ j -1]，
其次就是要處理障礙點，可以將起點和終點之間的障礙點處的f [ i ] [ j ]設為-1，
還要注意陣列越界的坑；答案要用long long，在此題的資料范圍中，最大的答案大到137846521561，這個數字用int已經存不下了，
代碼實作
DFS（未AC,40分）
//未 AC （DFS）
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int edx,edy,mx,my;
int dx[9]={0,1,2,2,1,-1,-2,-2,-1};
int dy[9]={0,2,1,-1,-2,-2,-1,1,2};
int v[MAXN][MAXN];//有無障礙
int flag[MAXN][MAXN];
int ct=0;
int dxz[2]={1,0};
int dyz[2]={0,1};
void DFS(int x,int y) //當前位置
{
if(x==edx&&y==edy)
{
ct++;
return;
}
if(x>edx || y>edy) return;
int tx,ty;
for(int i=0;i<=1;i++) //換成兩個 if還能再過一組資料
{
tx=x+dxz[i];
ty=y+dyz[i];
if(flag[tx][ty]==0&&v[tx][ty]==0&&tx<=edx&&ty<=edy)
{
flag[tx][ty]=1;
DFS(tx,ty);
flag[tx][ty]=0;
}
}
}
int main()
{
scanf("%d%d%d%d",&edx,&edy,&mx,&my);
memset(flag,0,sizeof(flag));
memset(v,0,sizeof(v));
for(int i=0;i<=8;i++)
v[mx+dx[i]][my+dy[i]]=-1; //障礙點
flag[0][0]=1;
DFS(0,0);
printf("%d",ct);
return 0;
}
AC代碼(動規)
//AC （DP）
#include<cstdio>
using namespace std;
const int MAXN=25;
int dx[8]={1,2,2,1,-1,-2,-2,-1};//除馬本身外的八個點 ，別漏掉馬本身
int dy[8]={2,1,-1,-2,-2,-1,1,2};
long long f[MAXN][MAXN]; //走到某點的方案數
int n,m,x,y;
int main()
{
scanf("%d%d%d%d",&n,&m,&x,&y);
f[x][y]=-1;
for(int i=0;i<8;i++)
if(x+dx[i]>=0&&x+dx[i]<=n&&y+dy[i]>=0&&y+dy[i]<=m) //判斷控制點是否在起點與終點之間，否則會RE
f[x+dx[i]][y+dy[i]]=-1; // 走不通 用-1 表示，用 0不好處理起點是否為控制點！
if(f[0][0]!=-1)
{
f[0][0]=1;//遞推初始狀態，到起點只有1種方法
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(f[i][j]!=-1)
{
if(i&&f[i-1][j]!=-1) f[i][j]+=f[i-1][j];//只能從兩個方向接近（左、上）
if(j&&f[i][j-1]!=-1) f[i][j]+=f[i][j-1];
}
printf("%lld\n",f[n][m]);
}
else printf("0\n");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/261088.html
標籤：其他
上一篇：免Root腳本之微信自動添加好友
下一篇：洛谷P2356 彈珠游戲