题目

Description

定的M*N的矩阵，其中的每个元素都是-10到10之间的整数，你的任务是从左上角（1，1），走到右下角（M,N），每一步只能向下或者向右，你所经过的方格里面的数字都必须被选取，请找出一条最合适的路，使得在路上被选取的数字之和是尽可能小的正整数。

Input

测试数据包括多组，以文件结尾为结束。
第一行：两个正整数M,N(2=<M,N<=10)；
接下来的M行：每行包括N个整数，是矩阵中每一行的N个元素。

Output

输出只有一行，就是一个整数，表示所选道路上数字之和所能达到的最小正整数。如果不能达到任何正整数，输出-1。

Sample Input

2 2
0 2
1 0

Sample Output

1

题解

由于要输出最小的正整数
因此单纯找最小是不行的,需要使用 DFS 深搜
0 不是正整数

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <bitset>
using namespace std;

const int maxn = 15;

int ans;
int Map[maxn][maxn];
int n,m;

void dfs(int x,int y,int sum) {
    if(x > n || y > m)
        return;
    int tsum = sum + Map[x][y];
    if(x == n && y == m)
        if(tsum > 0)
            ans = ((ans == -1) ? tsum : min(ans,tsum));

    dfs(x + 1,y,tsum);
    dfs(x,y + 1,tsum);
}

bool Do() {

    if(!(cin >> n >> m))
        return false;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++) {
            cin >> Map[i][j];
        }

    ans = -1;
    dfs(1,1,0);
    cout << ans << endl;

    return true;
}
int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    while(Do());
    return 0;
}