本文主要是介绍【hihocoder1290 微软2016校园招聘4月在线笔试C】【二维DP】 Demo Day 机器人遇到障碍向右走向下走 最少调整数使得左上角走到右下角，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Demo Day
-
4 8 ....bb.. ........ .....b.. ...bb...
样例输出 -
1
描述
You work as an intern at a robotics startup. Today is your company's demo day. During the demo your company's robot will be put in a maze and without any information about the maze, it should be able to find a way out.
The maze consists of N * M grids. Each grid is either empty(represented by '.') or blocked by an obstacle(represented by 'b'). The robot will be release at the top left corner and the exit is at the bottom right corner.
Unfortunately some sensors on the robot go crazy just before the demo starts. As a result, the robot can only repeats two operations alternatively: keep moving to the right until it can't and keep moving to the bottom until it can't. At the beginning, the robot keeps moving to the right.
rrrrbb.. ...r.... ====> The robot route with broken sensors is marked by 'r'. ...rrb.. ...bb...
While the FTEs(full-time employees) are busy working on the sensors, you try to save the demo day by rearranging the maze in such a way that even with the broken sensors the robot can reach the exit successfully. You can change a grid from empty to blocked and vice versa. So as not to arouse suspision, you want to change as few grids as possible. What is the mininum number?
输入
Line 1: N, M.
Line 2-N+1: the N * M maze.
For 20% of the data, N * M <= 16.
For 50% of the data, 1 <= N, M <= 8.
For 100% of the data, 1<= N, M <= 100.
输出
The minimum number of grids to be changed.
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 105, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n, m;
char a[N][N];
int f[N][N][2];
#include<assert.h>
int main()
{while (~scanf("%d%d", &n, &m)){for (int i = 0; i <= n + 1; ++i){for (int j = 0; j <= m + 1; ++j)a[i][j] = 'b';}for (int i = 1; i <= n; ++i)scanf("%s", a[i] + 1), a[i][m + 1] = 'b';assert(a[1][1] != 'b');MS(f, 63);f[1][0][1] = 0;for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){f[i][j][0] = f[i - 1][j][0] + (a[i][j] == 'b');f[i][j][1] = f[i][j - 1][1] + (a[i][j] == 'b');gmin(f[i][j][1], f[i][j][0] + (a[i + 1][j] != 'b'));gmin(f[i][j][0], f[i][j][1] + (a[i][j + 1] != 'b'));}}printf("%d\n", min(f[n][m][0], f[n][m][1]));}return 0;
}
/*
【题意】
给你一个n*m(100*100)的棋盘
一开始从左往右走，走到不能走就从上往下走
地图'b'代表障碍物，'.'代表空地
我们每步操作可以把'b'变为'.'或者把'.'变为'b'
问你最小操作数，使得我们从左上角走到右下角【类型】
DP【分析】
f[i][j][0]表示走到(i,j)，方向向下的最小操作数
f[i][j][1]表示走到(i,j)，方向向右的最小操作数
DP一下就可以AC啦【时间复杂度&&优化】
O(nm)*/这篇关于【hihocoder1290 微软2016校园招聘4月在线笔试C】【二维DP】 Demo Day 机器人遇到障碍向右走向下走 最少调整数使得左上角走到右下角的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
