Language: C++

#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>

using Pair = std::pair<int, int>;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int h, w;
unsigned int dp[1010][1010][32];
int map[1010][1010];

inline
bool checkBought(int y, int x, int mask) {
    if(x == 1 && y == 0) {
        return mask & 1 << 0;
    }else if(y == 1 && x == 0) {
        return mask & 1 << 1;
    }else if(y == 1 && x == -1) {
        return mask & 1 << 2;
    }else if(y == -1 && x == 1) {
		return mask & 1 << 3;
	}else if(y == 0 && x == 0) {
		return mask & 1 << 4;
	}
    return 0;
}

std::vector<Pair> wrapMask(int y, int x, int mask) {
	std::vector<Pair> pts;
	pts.reserve(5);
	
	if(mask & 1 << 0)
		pts.emplace_back(Pair{y, x - 1});
	if(mask & 1 << 1)
		pts.emplace_back(Pair{y - 1, x});
	if(mask & 1 << 2)
		pts.emplace_back(Pair{y - 1, x + 1});
	if(mask & 1 << 3)
		pts.emplace_back(Pair{y + 1, x - 1});
	if(mask & 1 << 4)
		pts.emplace_back(Pair{y, x});

	return pts;
}

int createMask(int y, int x, const std::vector<Pair>& pts) {
	int mask = 0;
	for(auto& p : pts) {
		if(p.first == y && p.second == x - 1)
			mask |= 1 << 0;
		else if(p.first == y - 1 && p.second == x)
			mask |= 1 << 1;
		else if(p.first == y - 1 && p.second == x + 1)
			mask |= 1 << 2;
		else  if(p.first == y + 1 && p.second == x - 1)
			mask |= 1 << 3;
		else if(p.first == y && p.second == x)
			mask |= 1 << 4;
	}

	return mask;
}

int main() {
    std::cin >> h >> w;
    memset(dp, -1, sizeof(dp));
    
    for(int i = 0; i < h; ++i) {
        std::string str;
        
        std::cin >> str;
        
        for(int j = 0; j < w; ++j) {
            if(str[j] == '.')
                map[i][j] = 0;
            else
                map[i][j] = str[j] - '0';
        }
    }
    

	dp[0][0][0] = 0;
	unsigned int ans = 1e9;
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            // 0th: ???, 1st: ??????, 2nd: ??????, 3rd: ??????, 4th: ??????
            for(int k = 0; k < 32; ++k) {
                if(j == 0 && (k & 1 << 0))
                    continue;
                if(i == 0 && (k & 1 << 1))
                    continue;
                if((i == 0 || j == w - 1) && (k & 1 << 2))
                    continue;
				if((j == 0 || i == h - 1) && (k & 1 << 3))
					continue;
				if(dp[i][j][k] == -1)
					continue;
                
                std::vector<Pair> pts;
                pts.reserve(4);
                for(int m = 0; m < 4; ++m) {
                    int py  = i + dy[m], px = j + dx[m];
                    
                    if(py < 0 || py >= h || px < 0 || px >= w)
                        continue;
                    
					if(map[py][px] != 0 &&  !checkBought(i - py, j - px, k))
						pts.emplace_back(Pair{py, px});
                }

				auto prevMaskVec = wrapMask(i, j, k);
				for(int m = 0; m < pts.size(); ++m) {
					auto clone = prevMaskVec;
					clone.reserve(5 + pts.size() - 1);

					int cost = 0;
					for(int n = 0; n < pts.size(); ++n) {
						if(m != n) {
							clone.emplace_back(pts[n]);
							cost += map[pts[n].first][pts[n].second];
						}
					}
					if(!checkBought(0, 0, k) && map[i][j] != 0) {
						cost += map[i][j];
						clone.emplace_back(Pair{i, j});
					}

					int mask = createMask(i + 1, j, clone);
					dp[i + 1][j][mask] = std::min(dp[i + 1][j][mask], dp[i][j][k] + cost);
					
					mask = createMask(i, j + 1, clone);
					dp[i][j + 1][mask] = std::min(dp[i][j + 1][mask], dp[i][j][k] + cost);
					
					if(i == h - 1 && j == w - 1)
						ans = std::min(ans, dp[i][j][k] + cost);
				}

				if(pts.empty()) {
					int cost = 0;
					if(!checkBought(0, 0, k) && map[i][j] != 0) {
						cost += map[i][j];
						prevMaskVec.emplace_back(Pair{i, j});
					}

					int mask = createMask(i + 1, j, prevMaskVec);
					dp[i + 1][j][mask] = std::min(dp[i + 1][j][mask], dp[i][j][k] + cost);
					
					mask = createMask(i, j + 1, prevMaskVec);
					dp[i][j + 1][mask] = std::min(dp[i][j + 1][mask], dp[i][j][k] + cost);
					
					if(i == h - 1 && j == w - 1)
						ans = std::min(ans, dp[i][j][k] + cost);

				}
            }
        }
    }

	std::cout << ans << std::endl;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:67:5: error: 'memset' was not declared in this scope
   67 |     memset(dp, -1, sizeof(dp));
      |     ^~~~~~
a.cc:6:1: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    5 | #include <vector>
  +++ |+#include <cstring>
    6 |