题目大意:卒A从( 0 , 0 )点要走到B点,其中有一个马,马所在的位置和马能到的位置为障碍点,不能通过。问走到B点一共有多少条路径。马的位置是固定不动的
算法思路： 我一开始想到dfs，结果只过了俩个点，后面三个超时了。后来想到用dp写。 先把怎么走到B点的路径模拟一遍（M为马的位置，X为马所能到达的位置） A 0 0 0 0 0 0 0 0 X 0 X 0 0 0 X 0 0 0 X 0 0 0 0 M 0 0 0 0 X 0 0 0 X 0 0 0 X 0 X 0 0 0 0 0 0 0 0 B 其中每个点的值代表的是当前这个点会有几条路径用过这个点（路径指的是从A到B的路径） 1 1 1 1 1 1 1 1 2 X 1 X 1 2 1 X 0 1 1 X 2 1 1 1 M 1 1 3 1 X 1 1 0 X 3 1 1 X 1 X 0 3 1 2 2 3 3 3 6 这样我们就能推导出状态转移方程 f[ i ][ j ] = f[i - 1][ j ] + f[ i ][j - 1]
需要注意的问题：
要注意数组越界；数据可能会很大，要开long long；如果直接用这个方程，A点会被直接覆盖成0； #include<bits/stdc++.h> using namespace std; int bx,by,mx,my; long long vis[25][25]; // 用来存到达这一个点路径 int flag[25][25]; int main() { cin >> bx >> by >> mx >> my; bx += 1; by += 1; mx += 1; my += 1; flag[mx][my] = 1; flag[mx - 2][my - 1] = 1; flag[mx - 2][my + 1] = 1; flag[mx - 1][my - 2] = 1; flag[mx - 1][my + 2] = 1; flag[mx + 1][my - 2] = 1; flag[mx + 1][my + 2] = 1; flag[mx + 2][my - 1] = 1; flag[mx + 2][my + 1] = 1; vis[1][1] = 1; for(int i = 1;i <= bx;i++) { for(int j = 1;j <= by;j++) { if(flag[i][j]) continue; if(i == 1 && j == 1) continue;//防止A点被覆盖 vis[i][j] = vis[i - 1][j] + vis[i][j - 1]; } } cout << vis[bx][by]; return 0; }