首页 > 代码库 > hiho150周 - 动态规划*

hiho150周 - 动态规划*

题目链接

一个n*m的迷宫由‘.’和‘b‘组成,从(1,1)走到(n,m),只能向右或者向下走,但遇到‘b’时才能改变方向,开始时方向向右。

问到达(n,m)至少改变几个位置上的值

/***********************************************************/

原来转移方程也可以这么优美

每个方格有两个状态,向右和向下

这两个状态均由左边和上边的两个方格四个状态转移得来

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))
#define MIN(a,b) ((a)<=(b)?(a):(b))
#define long long LL
#define OO 0x0fffffff
using namespace std;
#define RIGHT 0
#define DOWN 1

const int N = 111;
char maze[N][N];
int dp[N][N][2];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>maze[i];
    for(int i=0;i<n;i++) maze[i][m] = b;
    for(int j=0;j<m;j++) maze[n][j] = b;

    dp[0][0][0] = (maze[0][0]==b);
    dp[0][0][1] = (maze[0][0]==b)+(maze[0][1]!=b);
    for(int i=0;i<n;i++) for(int j=0;j<m;j++){
        if(!(i+j)) continue;
        dp[i][j][0] = dp[i][j][1] = OO;
        if(j-1>=0){
            dp[i][j][0] = MIN(dp[i][j-1][0],dp[i][j-1][1]+(maze[i+1][j-1]!=b));
            dp[i][j][1] = MIN(dp[i][j-1][0]+(maze[i][j+1]!=b),dp[i][j-1][1]+(maze[i+1][j-1]!=b)+(maze[i][j+1]!=b));
        }
        if(i-1>=0){
            dp[i][j][0] = MIN(dp[i][j][0],dp[i-1][j][0]+(maze[i-1][j+1]!=b)+(maze[i+1][j]!=b));
            dp[i][j][0] = MIN(dp[i][j][0],dp[i-1][j][1]+(maze[i+1][j]!=b));
            dp[i][j][1] = MIN(dp[i][j][1],dp[i-1][j][0]+(maze[i-1][j+1]!=b));
            dp[i][j][1] = MIN(dp[i][j][1],dp[i-1][j][1]);
        }
        dp[i][j][0]+=(maze[i][j]!=.);
        dp[i][j][1]+=(maze[i][j]!=.);
    }

    printf("%d\n",MIN(dp[n-1][m-1][0],dp[n-1][m-1][1]));
    return 0;
}

 

hiho150周 - 动态规划*