luogu1002 题解

希望大家都没有忘记，小学时老师曾讲过这样一个问题：

·	·	·
·	·	·
·	·	·

如图，小明家在图中的最左下角，学校在最右上角，请问：小明有多少种最短的方法到达学校？

那么老师讲，这个问题的解法是这样的：

1	3	6
1	2	3
0	1	1

像这样逐个标点，将原点上方和右方全部标为1，其他的格子都是它的左边一个和下边一个点上数字的和，由此计算出方法数。

而这个，正是我们学习的一大难点————动态规划。

真没想到，小学老师竟然讲过动态规划！

那么，这道题也是类似，只是加上了障碍。

话不多说，直接上题解。

  1 #include<bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 int n, m;//地图长宽
  6 
  7 long long a[25][25];//定义地图
  8 
  9 int horse_dirx[9] = {0,1,-1,1,-1,2,2,-2,-2};
 10 
 11 int horse_diry[9] = {0,2,2,-2,-2,1,-1,1,-1};//定义马的走向
 12 
 13 void setmap(int x, int y)//标记地图，预处理
 14 
 15 {
 16 
 17     int i;
 18 
 19     a[0][0] = 0;//起点不可走
 20 
 21     a[x][y] = 0;//马的位置不可走
 22 
 23     bool p = true;//判断横向纵向能否走到
 24 
 25     for (i = 1;i <= 8; i ++)
 26 
 27     {
 28 
 29         int nx = x + horse_dirx[i], ny = y + horse_diry[i];
 30 
 31         if(nx >= 0 && ny >= 0 && nx <= n && ny <= m)
 32             a[nx][ny] = 0;
 33 
 34     }//标记马的控制点，不可走
 35 
 36     for (i = 1; i <= m; i ++)
 37 
 38     {
 39 
 40         if(a[0][i] == -1)
 41 
 42         {
 43 
 44             if (p == true) a[0][i] = 1;
 45 
 46             else a[0][i] = 0;
 47 
 48         }
 49 
 50         else p = false;
 51 
 52     }//横向判断
 53 
 54     p = true;//重置变量
 55 
 56     for ( i = 1; i <= n; i ++)
 57 
 58     {
 59 
 60         if(a[i][0] == -1)
 61 
 62         {
 63 
 64             if (p == true)a[i][0] = 1;
 65 
 66             else a[i][0] = 0;
 67 
 68         }
 69 
 70         else p = false;
 71 
 72     }//纵向判断
 73 
 74 }
 75 
 76 int main()
 77 
 78 {
 79     ios :: sync_with_stdio(false)//输入输出优化
 80 
 81     memset (a,-1,sizeof(a));
 82 
 83     int i, j, x, y;
 84 
 85     cin >> n >> m >> x >> y;
 86 
 87     setmap(x, y);//定义、预处理
 88 
 89     for (i = 0; i <= n; i ++)
 90 
 91         for (j = 0; j <= m; j ++)
 92 
 93             if (a[i][j] == -1)
 94 
 95                 if (i != 0 && j != 0)a[i][j] = a[i-1][j] + a[i][j-1];//标记
 96 
 97     //  for (i = 0; i <= n; i ++)
 98 
 99     //  {
100 
101     //      for (j = 0; j < m; j ++)
102 
103     //          cout << a[i][j] << " ";
104 
105     //      cout << a[i][j] << endl;
106 
107     //  }检查时输出
108 
109     cout << a[n][m] << endl;
110 
111     return 0;
112 }

另一种思路：

#include<iostream>
#define L(i,k,mx,my) (i==mx+1||i==mx-1)&&(k==my+2||k==my-2)       
using namespace std;
int mx,my,m,n;
long long f[30][30]={1};           
bool li(int i,int k){
    if(i==mx&&k==my||i==0&&k==0) return 1;
    if(L(i,k,mx,my)||L(k,i,my,mx)) return 1;
    return 0;
}               
int main(){    
    cin>>n>>m>>mx>>my;
    for(int i=0;i<=n;i++)
        for(int k=0;k<=m;k++)
            if(!li(i,k)) f[i][k]=f[i][k==0? k:k-1]+f[i==0? i:i-1][k];         
    cout<<f[n][m];
    return 0;
}

部分选自luogu 题解。