天然货仓

题目描述

• 有一个天然形成的大坑，为台阶状结构，每个台阶的长度都为1，每个台阶的值为整数（正整数表示高于地平面，零表示与地平面平齐，负整数表示低于地平面）。
• 有一批同等规格的货品（长度为N，高度为1），货品只能平放，且货物的上表面不能超过地平面（深度为零），或者说，高于地平面的坑中也不可存放货物。
• 计算一个给定的大坑中最多可以放多少个货品？
• 如下图所示，[0,-1,-2,0] 组成的大坑，货品长度为2，可以放入1个货品（阴影矩形），返回1。

输入描述

• 输入依次为N，M，一维数组。
• N为该批次货物的长度（1 < N <= 100000），M为一维数组的长度（1 <= M <= 100000），
• 一维数组为大坑从左到右每个台阶的值（-10000 < 值 < 10000）。

输出描述

• 可以放入的货品总数，不能放入或异常返回 0。

样例 1

输入：

2

4

0,-1,-2,0

解释：

• 见样例 1 图示，坑中只能放入一个长度为 2 的货品，返回 1 。

思路：

我们可以把一维数组转化为二维数组，并且不需要考虑大于0的地区，我们只需要得出最小的数minNum。

然后转化为matrix[abs(minNum)][M]

例如样例1，

0	1	1	0
0	0	1	0

我们用0表示不可以放，1表示可以放。

然后对每个等于1的数开始DFS(只需要遍历右边即可),遍历到就把1变为0，遍历到了2个数，答案就加一，表示可以放下一个货物。

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int N;
int res = 0;

void dfs(vector<vector<int> >& martrix, int x, int y, int k){
    int m = martrix.size(), n = martrix[0].size();
    //base case
    if(x > m || y > n) return;
    //原来就不可以放
    if(martrix[x][y] == 0) return;
    //变为不可放
    martrix[x][y] = 0;
    k++;
    if(k == 2){
        //答案加一
        res++;
        return;
    }
    dfs(martrix, x, y + 1, k);
}

int main(){
    int M;
    cin >> N >> M;
    vector<int> nums(M);
    int minNum = INT_MAX;
    for(int i = 0; i < M; i++){
        cin >> nums[i];
        if(nums[i] < minNum){
            minNum = nums[i];
        }
    }
    //处理数组
    vector<vector<int> > matrix(abs(minNum), vector<int> (M, 0));
    for(int i = 0; i < M; i++){
        if(nums[i] < 0){
            int j = abs(nums[i]);
            int k = 0;
            while(k < j){
                matrix[k++][i] = 1;
            }
        }
    }
    //dfs
    for(int i = 0; i < matrix.size(); i++){
        for(int j = 0; j < matrix[0].size(); j++){
            if(matrix[i][j] == 1){
                dfs(matrix, i, j, 0);
            }
        }
    }
    cout << res << endl;
    return 0;
}