有一个方格迷宫，我们可以将它看作一个n*m的矩阵，每个方格表示一个房间，每个方格中都有数字。数字-1表示该房间内有陷阱，不能通过。如果格子里是>=0的数字，表示该房间中有怪兽，数字代表该怪兽的杀伤力，何老板通过该房将会失去对应数值的生命值。

一开始何老板位于左上角的方格(坐标[1,1]位置)，他要走到右下角的出口(坐标[n,m]位置)，每一步何老板可以往上、下、左、右走。 他想知道最少需要失去多少生命值就可以走出迷宫？

---

输入格式

第一行，两个整数n和m

接下来是一个由整数构成的n*m的矩阵，表示迷宫

输出格式 一个整数，表示最小失去的生命值。若无解，输出-1

样例输入

4 6

20 100 50 -1 -1 10

10 -1 50 10 10 5

10 -1 70 -1 10 -1

20 30 20 50 20 10

样例输出

190

#include <bits/stdc++.h>
using namespace std;
int n , m;
int Cost[35][35] , Map[35][35] , vis[35][35];
int Min = 0;
int ans = 0;
void dfs(int x , int y , int tot) {
	if(tot < Cost[x][y]) Cost[x][y] = tot;
	else return;
	if(tot >= ans) return;
	if(tot + (n + m - x - y) * Min >= ans) return;
	if(x == n && y == m) {
		if(tot < ans) ans = tot;
		return;
	}
	vis[x][y] = true;
	if(x - 1 >= 1 && Map[x - 1][y] != -1 && !vis[x - 1][y]) dfs(x - 1 , y , tot + Map[x - 1][y]);
	if(y - 1 >= 1 && Map[x][y - 1] != -1 && !vis[x][y - 1]) dfs(x , y - 1 , tot + Map[x][y - 1]);
	if(x + 1 <= n && Map[x + 1][y] != -1 && !vis[x + 1][y]) dfs(x + 1 , y , tot + Map[x + 1][y]);
	if(y + 1 <= m && Map[x][y + 1] != -1 && !vis[x][y + 1]) dfs(x + 1 , y , tot + Map[x][y + 1]);
	vis[x][y] = false;
	return;
}
int main() {
	cin >> n >> m;
	for(int i = 1 ; i <= n ; ++i) {
		for(int j = 1 ; j <= m ; ++j) {
			cin >> Map[i][j];
			if(Map[i][j] >= 0 && Min > Map[i][j]) Min = Map[i][j];
			if(Map[i][j] != -1) Cost[i][j] = INT_MAX;
		}
	}
	dfs(1 , 1 , 0);
	return 0;
}