AOJ 363.取数字问题

461

题目



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 深搜
| 99855821c596d99f44e1e450e27139358 | 不是正整数


代码


/*
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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论