做家教有什么好的资料网站,苏州seo关键词优化软件,网站开发项目答辩视频,手机免费制作ppt的软件下载题目传送门
思路
直接爆搜会TLE#xff0c;所以考虑进行DP。
由于卒只可以从左边和上面走#xff0c;所以走到(i,j)的路程总数为从上面走的路程总数加上从左边走的路程总数。我们用dp[i][j]表示从起点走到(i,j)的路程总数#xff0c;那么状态转移方程为#xff1a;
dp[…题目传送门
思路
直接爆搜会TLE所以考虑进行DP。
由于卒只可以从左边和上面走所以走到(i,j)的路程总数为从上面走的路程总数加上从左边走的路程总数。我们用dp[i][j]表示从起点走到(i,j)的路程总数那么状态转移方程为
dp[i][j]dp[i-1][j]dp[i][j-1];
再加上马的情况。
由于不能走到马和马的控制点所以我们用一个数组标记马和马的控制点到那个点的时候直接continue掉。另外要注意一下这道题的起点时0算马的坐标时会RE所以我们把所有的坐标加二遍历时从2开始。
代码
#includebits/stdc.h
#define endl \n;
#define int long long
using namespace std;
int n,m,mx,my,a[1011][1011],dp[1011][1011];//dp[i][j]表示从到(i,j)的路径条数
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnmmxmy;n,m,mx,my;n,m,mx,my;a[mx][my]1;a[mx1][my2]1;a[mx2][my1]1;a[mx-1][my2]1;a[mx-2][my1]1;a[mx1][my-2]1;a[mx2][my-1]1;a[mx-2][my-1]1;a[mx-1][my-2]1;dp[2][1]1; for(int i2;in;i){for(int j2;jm;j){if(!a[i][j])dp[i][j]dp[i-1][j]dp[i][j-1];}}coutdp[n][m];return 0;
}
