See: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

shortestpath.c

// See: https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
#include <stdio.h>

#define MAXN 40
#define MAXSTEP (40*40)

struct coord {
	unsigned char x;
	unsigned char y;
};

struct context {
	int **grid;
	short cache[MAXN][MAXN];
	struct coord stack[MAXN * MAXN];
	int top;
	int m;
	int n;
	int shortest;
};

static inline struct coord *
neighbor(struct context *ctx, struct coord *p, struct coord *n, int d) {
	static const int delta[4][2] = {
		{ -1, 0 },
		{ 1, 0 },
		{ 0, -1 },
		{ 0, 1 },
	};
	int x = (int)p->x + delta[d][0];
	if (x < 0 || x >= ctx->n)
		return NULL;
	int y = (int)p->y + delta[d][1];
	if (y < 0 || y >= ctx->m)
		return NULL;
	n->x = x;
	n->y = y;
	return n;
}

static inline int
distance(struct context *ctx, struct coord *p) {
	return (ctx->m - 1 - p->y) + (ctx->n - 1 - p->x);
}

static int 
shortest_grid(struct context *ctx) {
	while (ctx->top > 0) {
		struct coord p = ctx->stack[--ctx->top];
		int i;
		int step = ctx->cache[p.y][p.x];
		if (step + distance(ctx, &p) < ctx->shortest) {
			++step;
			for (i=0;i<4;i++) {
				struct coord n;
				if (neighbor(ctx, &p, &n, i) 
					&& ctx->grid[n.y][n.x] == 0
					&& step < ctx->cache[n.y][n.x] ) {
					ctx->cache[n.y][n.x] = step;
					ctx->stack[ctx->top++] = n;
				}
			}
		}
	}
	// ending point ( m -1, n -1 )
	int r = ctx->cache[ctx->m-1][ctx->n-1];
	if (r < ctx->shortest) {
		ctx->shortest = r;
	}
	return r;
}

static void
next_elimination(struct context *ctx) {
	int i,j,k;
	short obstacles[MAXN*MAXN];
	for (i=0;i<ctx->m;i++) {
		for (j=0;j<ctx->n;j++) {
			if (ctx->grid[i][j]) {
				// Obstacle
				struct coord p = { j, i };
				struct coord n;
				int last = ctx->cache[i][j];
				int shortest = last;
				for (k=0;k<4;k++) {
					if (neighbor(ctx, &p, &n, k) && ctx->cache[n.y][n.x] + 1 < shortest) {
						shortest = ctx->cache[n.y][n.x] + 1;
					}
				}
				if (shortest < last) {
					int c = ctx->top++;
					struct coord *t = &ctx->stack[c];
					t->x = p.x;
					t->y = p.y;
					obstacles[c] = shortest;
				}
			}
		}
	}
	for (i=0;i<ctx->top;i++) {
		struct coord *p = &ctx->stack[i];
		ctx->cache[p->y][p->x] = obstacles[i];
	}
}

int
shortestPath(int** grid, int gridSize, int* gridColSize, int k ){
	struct context ctx;
	ctx.shortest = MAXSTEP;
	ctx.grid = grid;
	ctx.m = gridSize;
	ctx.n = gridColSize[0];
	ctx.top = 1;
	// staring point (0,0)
	ctx.stack[0].x = 0;
	ctx.stack[0].y = 0;
	int i,j;
	for (i=0;i<ctx.m;i++) {
		for (j=0;j<ctx.n;j++) {
			ctx.cache[i][j] = MAXSTEP;
		}
	}
	ctx.cache[0][0] = 0;

	int r = shortest_grid(&ctx);
	for (i=1;i<=k;i++) {
		next_elimination(&ctx);
		int s = shortest_grid(&ctx);
		if (s < r) {
			r = s;
			if (r == ctx->m -1 + ctx->n - 1)
				return r;
		}
	}
	if (r == MAXSTEP)
		return -1;
	return r;
}

int
main() {
	int grid[5][3] = {
		{ 0,0,0 },
		{ 1,1,0 },
		{ 0,0,0 },
		{ 0,1,1 },
		{ 0,0,0 },
	};
	int *lines[5] = { grid[0], grid[1], grid[2], grid[3], grid[4] };
	int gridSize = 5;
	int gridColSize[5] = { 3,3,3,3,3 };
	int d = shortestPath(lines, gridSize, gridColSize, 1);
	printf("shortest path = %d\n", d);
	return 0;
}

膜一下云大，贴一个我的

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        const int dir[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int n = grid.size(), m = grid[0].size();
        vector<vector<vector<int>>> vis(n, vector<vector<int>>(m, vector<int>(n*m+1,0x3fff3fff)));
        queue<tuple<int,int,int>> q;// point, step, k
        q.push({0,0,k});
        while(!q.empty()){
            auto now = q.front();
            q.pop();
            if(get<0>(now) == n*m-1) return get<1>(now);
            // cout<<"("<<(get<0>(now) / m)<<","<<(get<0>(now) % m)<<")"<<"-"<<get<1>(now)<<"-"<<get<2>(now)<<endl;
            for(auto& i : dir){
                int xx = (get<0>(now) / m) + i[0];
                int yy = (get<0>(now) % m) + i[1];
                if(xx>-1&&xx<n&&yy>-1&&yy<m){
                    int curK = get<2>(now);
                    curK -= grid[xx][yy];
                    if(curK < 0) continue;
                    if(vis[xx][yy][curK] <= get<1>(now) + 1) continue;
                    vis[xx][yy][curK] = get<1>(now) + 1;
                    q.push({xx*m+yy, get<1>(now) + 1, curK});
                }
            }
        }
        return -1;
    }
};