hiho_1290_demo_day-白红宇

hiho_1290_demo_day

阅读量：6709 次

发布时间：2019-06-25

本文共 2191 字，大约阅读时间需要 7 分钟。

题目大意

一个MxN的矩阵，矩阵中的有些方格中有障碍物，有些没有，有一个机器人从左上角出发，它只能有两种移动方式：一直向右移动，直到遇到障碍物；一直向下移动，直到遇到障碍物。

现在可以将矩阵中的方格进行变换：如果方格中没有障碍物，则可以加入障碍物；如果方格中有障碍物，则可以清楚障碍物。求使得机器人可以从左上角移动到右下角的最少的方格变动个数。

题目链接：

题目分析

搜索复杂度太高，由于机器人只能向右或者向下移动，这就可以考虑使用动态规划进行状态的转移。设状态 dp[i][j][0] 表示robot从左侧进入方格(i,j)所需要改变的最少的方格数；dp[i][j]表示robot从上侧进入方格(i, j)时所需要改变的最少的方格数。

这道题目是微软的暑期实习在线笔试题，考试期间做的时候由于对c/c++中的运算符优先级没有掌握准确，left_min + (gMap[i - 1][j - 1] == 'b') 中没有加括号，导致结果出错。基础很重要啊！运算优先级不确定的地方，加括号！

另外，动态规划的初始值很重要，要仔细思考！

实现

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              using namespace std;#define MAX_NUM 105char gMap[MAX_NUM][MAX_NUM];int dp[MAX_NUM][MAX_NUM][2];//dp[i][j][0] robot 从左侧进入(i, j)最少需要改变的次数//dp[i][j][1] robot 从上册进入(i, j)最少需要改变的次数#define INF 1 << 29void debug(int m, int n){ for (int i = 1; i <= m; i++){ for (int j = 1; j <= n; j++){ cout << "(" << i << ", " << j << ", 0) = " << dp[i][j][0] << ", "; cout << "(" << i << ", " << j << ", 1) = " << dp[i][j][1] << endl; } cout << endl; }}int min(int a, int b){ return a < b ? a : b;}int main(){ int m, n; scanf("%d %d", &m, &n); for (int i = 0; i < m; i++){ getchar(); for (int j = 0; j < n; j++){ scanf("%c", &gMap[i][j]); dp[i + 1][j + 1][0] = INF; dp[i + 1][j + 1][1] = INF; } } int count = 0; for (int i = 1; i <= n; i++){ if (gMap[0][i - 1] == 'b') count++; dp[1][i][0] = count; dp[1][i][1] = INF; } count = (gMap[0][1] != 'b'); for (int i = 1; i <= m; i++){ if (gMap[i - 1][0] == 'b') count++; dp[i][1][1] = count; dp[i][1][0] = INF; } dp[1][1][0] = 0; for (int i = 2; i <= m; i++){ for (int j = 2; j <= n; j++){ int up_0 = dp[i - 1][j][0]; int up_1 = dp[i - 1][j][1]; int up_min = up_0 + !(j == n|| gMap[i - 2][j] == 'b'); up_min = min(up_min, up_1); dp[i][j][1] = min(dp[i][j][1], up_min + (gMap[i - 1][j - 1] == 'b')); int left_0 = dp[i][j - 1][0]; int left_1 = dp[i][j - 1][1]; int left_min = left_1 + !(i == m || gMap[i][j - 2] == 'b'); left_min = min(left_min, left_0); dp[i][j][0] = min(dp[i][j][0], left_min + (gMap[i - 1][j - 1] == 'b')); } } int result = dp[m][n][0] < dp[m][n][1] ? dp[m][n][0] : dp[m][n][1]; cout << result << endl; return 0;}

转载地址：http://oialo.baihongyu.com/

你可能感兴趣的文章