时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
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.
注记：
动态规划的一道题，后悔当时没有看通过率先做了第二道，第二题没有熟练掌握Trie结果处理超时了！
这题就是状态麻烦点，我的处理方式是在当前位置就判断右侧及下侧的通行情况，必要时做出改变，然后继续。因此注意点是一开始就被[0][0]位置blocked的情况。
以(x位置,y位置,当前方向)为一个三元组，可以保存唯一的状态结果，避免重复递归。
代码:
未经详细测试，待测试！感觉自己的编码能力还是有限，欢迎过客提出意见。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int FAIL = -32767;
struct St {
bool hasRight;
bool hasDown;
int rightBest;
int downBest;
St(){
hasRight = false;
hasDown = false;
}
void setVal(bool movR, int val) {
if (movR) {
hasRight = true;
rightBest = val;
}
else {
hasDown = true;
downBest = val;
}
}
bool hasVal(bool movR) {
if (movR)
return hasRight;
else
return hasDown;
}
int getVal(bool movR) {
if (movR)
return rightBest;
else
return downBest;
}
};
int legalMin(int x, int y) {
if (x < 0) return y;
else if (y < 0) return x;
else return x<y ? x : y;
}
int moveMaze(const vector<string>& maze, int i, int j, bool movR, vector<vector<St>>& storedMap) {
//cout << '.';
if ((i == maze.size() - 1) && (j == maze[0].size() - 1)) {
//Out of maze and finished
return 0;
}
else if ((i == maze.size()) || (j == maze[0].size())) {
//Reach boundary
return FAIL;
}
if (storedMap[i][j].hasVal(movR)) {
//cout << "HIT!" << i << ", " << j << ", "<< movR << endl;
return storedMap[i][j].getVal(movR);
}
int right = FAIL;
int down = FAIL;
if (movR) {
//Moving towards right side
if (j == maze[0].size() - 1 || maze[i][j + 1] == '.') {
right = moveMaze(maze, i, j + 1, movR, storedMap);
if (j == maze[0].size() - 1)
down = moveMaze(maze, i + 1, j, false, storedMap);
else
down = 1 + moveMaze(maze, i + 1, j, false, storedMap);
}
else {
//blocked
right = 1 + moveMaze(maze, i, j + 1, movR, storedMap);
if (i == maze.size() - 1 || maze[i + 1][j] == '.')
down = moveMaze(maze, i + 1, j, false, storedMap);
else
down = 1 + moveMaze(maze, i + 1, j, false, storedMap);
}
}
else {
if (i == maze.size() - 1 || maze[i + 1][j] == '.') {
//Move down safely
down = moveMaze(maze, i + 1, j, movR, storedMap);
if (i == maze.size() - 1)
right = moveMaze(maze, i, j + 1, true, storedMap);
else
right = 1 + moveMaze(maze, i, j + 1, true, storedMap);
}
else {
//blocked
down = 1 + moveMaze(maze, i + 1, j, movR, storedMap);
if (j == maze[0].size() - 1 || maze[i][j + 1] == '.')
right = moveMaze(maze, i, j + 1, true, storedMap);
else
right = 1 + moveMaze(maze, i, j + 1, true, storedMap);
}
}
int result = legalMin(down, right);
storedMap[i][j].setVal(movR, result);
return result;
}
int main() {
int N, M;
cin >> N >> M;
vector<string> maze;
for (int i = 0; i<N; i++) {
string str;
cin >> str;
maze.push_back(str);
}
vector<vector<St>> storedMap;
for (int i = 0; i < N; i++) {
vector<St> line;
for (int j = 0; j < M; j++) {
line.push_back(St());
}
storedMap.push_back(line);
}
int result;
if(maze[0][0] == '.')
result = moveMaze(maze, 0, 0, true, storedMap);
else //[0][0]就是'b'
result = 1 + moveMaze(maze, 0, 0, true, storedMap);
cout << result << endl;
return 0;
}