1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
using namespace std;
const char block = 'b';
inline bool OutBoard(int N, int M, int i, int j) {
    return !(i >= 0 && i < N && j >= 0 && j < M);
}
int MinGridChanged(int N, int M, vector< vector<char> > &maze) {
    //source: (0, 0), destination: (N-1, M-1)
    pair<int, int> source(0, 0);
    pair<int, int> destination(N - 1, M - 1);
    //only move to right or bottom is allowed
    const int right = 0;
    const int bottom = 1; 
    const int maxChange = 1000;
    //move operator in different direction
    int movei[2] = { 0, 1 };
    int movej[2] = { 1, 0 };
    //minGridChange[i][j][direc] represent the minimum grid changes if move to (i, j) in different direction 
    vector< vector< vector<int> > > minGridChange(N, vector< vector<int> >(M, vector<int>(2, maxChange)));
    //init the minGraidChange in source. (At the beginning ,the robot keeps moving to the right.)
    minGridChange[0][0][right] = 0;
    if(maze[0][0] == block){
        minGridChange[0][0][right]++;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX