1368. 使网格图至少有一条有效路径的最小代价 搜索+剪枝

题目：1368. 使网格图至少有一条有效路径的最小代价
链接：https://leetcode-cn.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/
思路：定义dp[i][j]表示到达(i, j)需要的修改的最少次数。核心：如果到(i, j)时，dp[i][j]访问过，且更小，那么此次不能达到(i, j)，前面肯定更优。
把所有可能的情况走一遍，O(n)=n*m*2(n+m)。


const int maxn = 105;
const int r = 1;
const int l = 2;
const int d = 3;
const int u = 4;
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 1,2,3,4  posi = grid[i][j]-1
struct G {
    int x, y;
    int step;
    G():x(),y(),step(){}
    G(int x, int y):x(x),y(y),step(0){}
};

class Solution {
public:
    int dp[maxn][maxn]; // 定义dp[i][j]表示到达(i, j)需要的修改的最少次数。核心：如果到(i, j)时，dp[i][j]访问过，且更小，那么不能此次不能达到(i, j)，前面肯定更优。
public:
    int minCost(vector< vector<int> >& grid) {
        int n, m;
        n = grid.size();
        m = grid[0].size();
        memset(dp, -1, sizeof dp);
        // 队列，dfs应该都行。
        // 理论上有尽头，且不会很多。 <= n*m*2(m+n)
        queue<G> q;
        G g(0, 0);
        q.push(g);
        dp[0][0] = 0;
        int x, y, step;
        while(q.size()>0) {
            g = q.front();
            // cout << "(" << g.x << ", " << g.y << ")" << "step: " << g.step <<endl;
            q.pop();
            G t;
            for(int i = 0; i < 4; i++) {
                x = dir[i][0]+g.x;
                y = dir[i][1]+g.y;
                if (x < 0 || y < 0 || x >= n || y >= m) { // 超出范围。
                    continue;
                }
                // 计算step
                if (grid[g.x][g.y]-1 == i) {
                    step = g.step;
                } else {
                    step = g.step + 1;
                }
                if (dp[x][y] != -1) {
                    if (dp[x][y] > step) {
                        t.x = x;
                        t.y = y;
                        t.step = step;
                        dp[x][y] = step;
                        if (x==n-1&&y==m-1) {
                            continue;
                        }
                        q.push(t);
                    }
                } else {
                    t.x = x;
                    t.y = y;
                    t.step = step;
                    dp[x][y] = step;
                    if (x==n-1&&y==m-1) {
                        continue;
                    }
                    q.push(t);
                }
            }
        }
        return dp[n-1][m-1];
    }
};