360企业安全,最长递增路径
``````#include <bits/stdc++.h>using namespace std;void dfs(vector<vector<int> > &m, int row, int col, vector<int> &path, vector<int> &res, vector<vector<int> > &visited){if(path.size() > res.size())res = path;if(row < 0 || row > m.size() - 1 || col < 0 || col > m[0].size() - 1)return;//has visitedif(visited[row][col])return;visited[row][col] = 1;path.push_back(m[row][col]);if(row + 1 < m.size() && m[row + 1][col] > m[row][col])dfs(m, row + 1, col, path, res, visited);if(col + 1 < m[0].size() && m[row][col + 1] > m[row][col])dfs(m, row, col + 1, path, res, visited);if(row - 1 >= 0 && m[row - 1][col] > m[row][col])dfs(m, row - 1, col, path, res, visited);if(col - 1 >= 0 && m[row][col - 1] > m[row][col])dfs(m, row, col - 1, path, res, visited);//backtracingvisited[row][col] = 0;path.pop_back();return;}int longpath(vector < vector < int > > matrix) {if(matrix.size() == 0)return 0;vector<vector<int> > visited(matrix.size(), vector<int>(matrix[0].size(), 0));vector<int> res;for(int row = 0; row < matrix.size(); row++){for(int col = 0; col < matrix[0].size(); col++){vector<int> path;dfs(matrix, row, col, path, res, visited);}}return res.size();}int main(){vector < vector < int > > matrix;matrix = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};cout << longpath(matrix) << endl;;}
我的大致思路,但是测试用例我在本地测试的不对,更坑的是,复制上去的时候,少复制了头文件的尖括号,导致编译一直失败,然后系统自动提交了,悲剧,之前还以为会2道ac,结果时间根本不够。
#360公司##笔试题目#