LeetCode/329.Longest_Increasing_Path_in_a_Matrix.cpp at master · yuandong1222/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int longestIncreasingPathForCell(
            vector<vector<int> >& matrix,
            vector<vector<int> >& result,
            int i,
            int j) {

        if (result[i][j] != 0) {
            return result[i][j];
        }

        result[i][j] = 1;
        if (i > 0 && matrix[i - 1][j] < matrix[i][j]) {
            result[i][j] = max(result[i][j], 1 + longestIncreasingPathForCell(matrix, result, i - 1, j));
        }
        if (i < matrix.size() - 1 && matrix[i + 1][j] < matrix[i][j]) {
            result[i][j] = max(result[i][j], 1 + longestIncreasingPathForCell(matrix, result, i + 1, j));
        }
        if (j > 0 && matrix[i][j - 1] < matrix[i][j]) {
            result[i][j] = max(result[i][j], 1 + longestIncreasingPathForCell(matrix, result, i, j - 1));
        }
        if (j < matrix[0].size() - 1 && matrix[i][j + 1] < matrix[i][j]) {
            result[i][j] = max(result[i][j], 1 + longestIncreasingPathForCell(matrix, result, i, j + 1));
        }

        return result[i][j];
    }
    int longestIncreasingPath(vector<vector<int> >& matrix) {
        int max = 0;

        vector<vector<int> > result(matrix.size());
        for (int i = 0; i < matrix.size(); i++) {
            result[i].resize(matrix[0].size());
            for (int j = 0; j < matrix[0].size(); j++) {
                result[i][j] = 0;
            }
        }

        for (int i = 0; i <  matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                int cell_max = longestIncreasingPathForCell(matrix, result, i, j);
                max = cell_max > max ? cell_max : max;
            }
        }

        return max;
    }
};

int main(int argc, char** argv) {
    vector<vector<int> > result(3);
    for (int i = 0; i < 3; i++) {
        result[i].resize(3);
    }
    result[0][0] = 9;
    result[0][1] = 9;
    result[0][2] = 4;

    result[1][0] = 6;
    result[1][1] = 6;
    result[1][2] = 8;

    result[2][0] = 2;
    result[2][1] = 1;
    result[2][2] = 1;

    Solution solution;
    return solution.longestIncreasingPath(result);
}