4 solutions
-
1
代码较长
#include <iostream> using namespace std; int fx[10]={0,-2,-1,1,2,2,1,-1,-2}; int fy[10]={0,1,2,2,1,-1,-2,-2,-1};//移动 int bx,by,mx,my; long long f[25][25];//dp bool s[25][25];//地图 //void print(){ // for(int i=0;i<=bx;i++){ // for(int j=0;j<=by;j++) cout<<f[i][j]<<" "; // cout<<endl; // } // cout<<endl; //} //void out(){ // for(int i=0;i<=bx;i++){ // for(int j=0;j<=by;j++) cout<<s[i][j]<<" "; // cout<<endl; // } // cout<<endl; //} int main(){ cin>>bx>>by>>mx>>my; //初始条件 for(int i=0;i<=8;i++) if(mx+fx[i]>=0&&mx+fx[i]<=bx&&my+fy[i]>=0&&my+fy[i]<=by) s[mx+fx[i]][my+fy[i]]=true; for(int i=0;i<=bx;i++){ if(s[i][0]==false) f[i][0]=1; else break; } for(int i=0;i<=by;i++){ if(s[0][i]==false) f[0][i]=1; else break; } //递推 for(int i=1;i<=bx;i++){ for(int j=1;j<=by;j++){ if(s[i][j]==false) f[i][j]=f[i-1][j]+f[i][j-1]; } } cout<<f[bx][by]<<endl; return 0; }-
C23pengweixuan
@ 2024-7-18 19:22:24
再提供一种深搜做法
#include<bits/stdc++.h> #define sc scanf #define pr printf #define int long long using namespace std; int bx,by; int mx,my; bool stop[25][25]={}; //马的控制点 int Dx[9]={0,-2,-1,1,2,2,1,-1,-2}; int Dy[9]={0,1,2,2,1,-1,-2,-2,-1}; //走的方向 int dp[25][25]={}; //dp表存数据 int dfs(int x,int y){ //dfs开始遍历 if(x<0||x>bx||y<0||y>by) return 0; if(stop[x][y]) return 0; //越界退出 if(dp[x][y]) return dp[x][y]; //记忆化 int ii=0,jj=0; ii=dfs(x-1,y); jj=dfs(x,y-1); return dp[x][y]=ii+jj; //返回 + 存dp } signed main(){ sc("%lld%lld%lld%lld",&bx,&by,&mx,&my); for(int i=0;i<=8;i++) if(mx+Dx[i]>=0&&mx+Dx[i]<=bx&&my+Dy[i]>=0&&my+Dy[i]<=by) stop[mx+Dx[i]][my+Dy[i]]=true; for(int i=0;i<=bx;i++) if(stop[i][0]==false) dp[i][0]=1; else break; for(int i=0;i<=by;i++) if(stop[0][i]==false) dp[0][i]=1; else break; //以上一坨都是初始化 dfs(bx,by); //倒着遍历 pr("%lld",dp[bx][by]); return 0; }
-
-
0
C24yaoyijun LV 4 @ 2024-7-11 21:55:09
有个简单的
#include <iostream> using namespace std; long long dp[25][25]; int xx[9] = {0,1,1,2,2,-1,-1,-2,-2}; int yy[9] = {0,-2,2,1,-1,2,-2,1,-1}; bool b[25][25]; int main(){ int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; for (int i = 0;i<=8;i++){ if (x2+xx[i] < 0 or y2+yy[i] < 0){ continue; } b[x2+xx[i]][y2+yy[i]] = true; dp[x2+xx[i]][y2+yy[i]] = 0; } for (int i = 0;i<=x1;i++){ for (int j = 0;j<=y1;j++){ if (b[i][j] == true) continue; else if (i == 0 and j == 0) dp[i][j] = 1; else if (i == 0) dp[i][j] = dp[i][j-1]; else if (j == 0) dp[i][j] = dp[i-1][j]; else dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } cout << dp[x1][y1]; return 0; } -
-1
C24wanghongming
LV 8
@ 2025-3-14 13:19:46
思路：每一个都为上面与左边的路径和
#include <iostream> using namespace std; int px[10]={0,-2,-1,1,2,2,1,-1,-2}; int py[10]={0,1,2,2,1,-1,-2,-2,-1}; int n,m,cx,cy; long ans[25][25]={{1}}; bool check(int x,int y){ for(int i=0;i<9;i++)if(x+px[i]==cx&&y+py[i]==cy)return false; return true; } int main(){ cin>>n>>m>>cx>>cy; for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){ if(i>0&&check(i-1,j))ans[i][j]+=ans[i-1][j]; if(j>0&&check(i,j-1))ans[i][j]+=ans[i][j-1]; } cout<<ans[n][m]; return 0; }##压行版
#include<bits/stdc++.h> using namespace std; long px[10]={0,-2,-1,1,2,2,1,-1,-2},py[10]={0,1,2,2,1,-1,-2,-2,-1},n,m,cx,cy,ans[25][25]={{1}}; bool check(int x,int y){ for(int i=0;i<9;i++)if(x+px[i]==cx&&y+py[i]==cy)return false; return true; } int main(){ cin>>n>>m>>cx>>cy; for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){ if(i>0&&check(i-1,j))ans[i][j]+=ans[i-1][j]; if(j>0&&check(i,j-1))ans[i][j]+=ans[i][j-1]; } cout<<ans[n][m]; return 0; }-
h_h @ 2025-3-19 19:22:40
首先大力表扬ans和chck，但是猴哥以后发题解追求点高质量（讲解下易错点之类的），压行别压过头了
-
-
-1
C23chenxinglin
LV 9
@ 2024-7-19 19:25:18
正常人都想得出的解法#include <bits/stdc++.h> using namespace std; long long a[100][100]; bool b[100][100]; int main(){ int n , m , x , y; cin >> n >> m >> x >> y; x++; y++; n++; m++; b[x][y]=1; b[x + 1][y + 2] = 1; b[x + 1][y - 2] = 1; b[x - 1][y + 2] = 1; b[x - 1][y - 2] = 1; b[x + 2][y + 1] = 1; b[x + 2][y - 1] = 1; b[x - 2][y + 1] = 1; b[x - 2][y - 1] = 1; a[1][1] = 1; for (int i = 1;i <= n;i++){ for (int j = 1;j <= m;j++){ if (i == 1 && j == 1){ j++; } if(b[i][j] == 0){ a[i][j] = a[i - 1][j] + a[i][j - 1]; } } } cout << a[n][m]; return 0; }
- 1