公司在网站做广告怎么做分录,学生如何建设网站,关键词名词解释,站外推广内容策划题干#xff1a;
小乐乐一天天就知道玩#xff0c;这一天又想玩象棋。 我们都知道马走日。 现在给定一个棋盘#xff0c;大小是n*m,把棋盘放在第一象限#xff0c;棋盘的左下角是(0,0),右上角是(n - 1, m - 1); 小乐乐想知道#xff0c;一个马从左下角(0, 0)开始#…题干
小乐乐一天天就知道玩这一天又想玩象棋。 我们都知道马走日。 现在给定一个棋盘大小是n*m,把棋盘放在第一象限棋盘的左下角是(0,0),右上角是(n - 1, m - 1); 小乐乐想知道一个马从左下角(0, 0)开始走了k步之后刚好走到右上角(n - 1, m - 1)的方案数。
输入描述:
输入多组样例输入每组一行三个整数n, m, k(1 n, m, k 200),如题目所示。
输出描述:
输出输出答案 mod 1000000007 示例1
输入
复制
4 4 2
输出
复制
2
解题报告 跪了一晚上发现是因为写成了tyxny[k]了看来是太久不写地图的dfs了、、老毛病又犯了、、难受难受
AC代码1记忆化搜索 其实也可以直接在main函数中dp[n][m][0]1这样在写dfs的时候就不需要特判一下出口了、、总的来说是个不算难的好题、、
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll dp[205][205][205];
const ll mod 1000000007;
int n,m,t;
int nx[9] {-2,-1,1,2,2,1,-1,-2};
int ny[9] {1,2,2,1,-1,-2,-2,-1};
bool ok(int x,int y) {if(x1xny1ym) return 1;else return 0;
}
ll dfs(int x,int y,int res) {if(x n y m res 0) return dp[n][m][res]1;if(res 0) return 0;if(dp[x][y][res]!-1) return dp[x][y][res];ll sum 0;int tx,ty;for(int k 0; k8; k) {tx x nx[k];ty y ny[k];if(ok(tx,ty) 0) continue;//if(res0) continue;sum dfs(tx,ty,res-1);sum % mod;}dp[x][y][res] sum;return sum;}
int main()
{while(~scanf(%d%d%d,n,m,t)) {memset(dp,-1,sizeof dp);printf(%lld\n,dfs(1,1,t)%mod);} return 0 ;}
其中也有一个细节值得注意这样搜索的正确性首先因为你表示的状态体现出了剩余的步数所以不用怕走过去下一步又走回来这种情况因为在状态设计中这属于不同的状态所以没事再就是不用怕会出现环也就是绕一圈状态又绕回来了。。原因就是因为你的dfs都是res-1的操作所以整个就是一个DAG图不必要担心会出现未完成值的重复调用。。
AC代码2三种直接dp
#includebits/stdc.h
using namespace std;
#define LL long long
#define pii pairint,int
#define x first
#define y second
#define mp make_pair
//#define debug
const LL mod1e97;
LL f[205][205][205];
int fx[8][2]{1,2,1,-2,2,1,2,-1,-1,-2,-1,2,-2,-1,-2,1};
void B(){int n,m,K;while(cinnmK){memset(f,0,sizeof(f));f[1][1][0]1;for(int k0;kK;k){for(int i1;in;i){for(int j1;jm;j){if(f[i][j][k]){for(int o0;o8;o){if(ifx[o][0]1 jfx[o][1]1)(f[ifx[o][0]][jfx[o][1]][k1]f[i][j][k])%mod; }}}}}coutf[n][m][K]endl;}
}
int main(){B();return 0;
}#includebits/stdc.h
#define mod 1000000007
using namespace std;
int dp[205][205][205];
int dis[8][2]{2,1,2,-1,-2,1,-2,-1,1,2,1,-2,-1,2,-1,-2};
int main()
{int n,m,k;while(scanf(%d%d%d,n,m,k)!EOF){memset(dp,0,sizeof(dp));dp[1][1][0]1;for(int s1;sk;s)for(int i1;in;i)for(int j1;jm;j){int temp0;for(int h0;h8;h){int xidis[h][0];int yjdis[h][1];if(x1xny1ym)tempdp[x][y][s-1],temp%mod;}dp[i][j][s]temp;}printf(%d\n,dp[n][m][k]);
}return 0;
}#include bits/stdc.h
using namespace std;
int dp[205][205][205];
const int mod1000000007;
int nex[8][2]{{1,2},{2,1},{-1,-2},{-2,-1},{2,-1},{1,-2},{-1,2},{-2,1}};
int main()
{int n,m,d;while(~scanf(%d %d %d,n,m,d)){memset(dp,0,sizeof(dp));dp[1][1][0]1;for(int k1;kd;k){for(int i1;in;i)for(int j1;jm;j){for(int s0;s8;s){int xinex[s][0];int yjnex[s][1];if(x1||y1||xn||ym) continue;dp[i][j][k](dp[i][j][k]dp[x][y][k-1])%mod;}}}printf(%d\n,dp[n][m][d]);}return 0;
}
看了dp的代码发现dp好像也不是很难写、、、也不是很难想因为这种状态也是符合递推的。。
简单的一个题着实又让我对动态规划有了新的理解
考虑改编 改编成一个n*m的方格但是终点不是右上角的那个[n,m]点而是新输入的两个点这样进行dp但是可能有个问题就是可能搜索的范围会大了很多啊。。
