过河卒--记忆化搜索

1.dfs正常做，记得还原，bo数组及时还原成false

2.事件类做法，到终点返回1，记作一次合理路线/方法

类似的李白打酒，地宫取宝

P1002 [NOIP 2002 普及组] 过河卒 - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
int n,m,x,y;
int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
bool bo[35][35];
ll dp[35][35];
ll dfs(int x,int y)
{if(x==n&&y==m) return 1;if(x<0||x>n||y>m||y<0) return 0;if(dp[x][y]!=-1) return dp[x][y];ll res=0;if(x+1<=n&&!bo[x+1][y]){bo[x+1][y]=true;res+=dfs(x+1,y);bo[x+1][y]=false;	} if(y+1<=m&&!bo[x][y+1]){bo[x][y+1]=true;res+=dfs(x,y+1);bo[x][y+1]=false;	}return dp[x][y]=res;
}
void solve()
{cin>>n>>m>>x>>y;bo[x][y]=true;for(int i=0;i<8;i++){int tx=x+dx[i];int ty=y+dy[i];if(tx>=0&&tx<=n&&ty>=0&&ty<=m){bo[tx][ty]=true;}}bo[0][0]=true;memset(dp,-1,sizeof(dp));cout<<dfs(0,0);
} 
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}