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 visited
if(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);
//backtracing
visited[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公司##笔试题目#
全部评论
我只过了67%,不知道忽略了什么🤣
点赞 回复 分享
发布于 2019-04-24 20:42
思路差不多,我的AC了 import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Main { /*请完成下面这个函数,实现题目要求的功能 当然,你也可以不按照下面这个模板来作答,完全按照自己的想法来 ^-^  ******************************开始写代码******************************/     static int longpath(int[][] matrix) {         int rows = matrix.length;         int cols = matrix[0].length;         int path = Integer.MIN_VALUE;         for(int i=0;i<rows;i++) {             for(int j=0;j<cols;j++) {                 boolean[][] visited = new boolean[rows][cols];                 int res = helper(matrix, rows, cols, i, j, visited);                 System.out.println(res);                 path = Math.max(path, res);             }         }         return path;     } /******************************结束写代码******************************/     public static int helper(int[][] matrix, int rows, int cols, int x, int y, boolean[][] visited) {         if(x<0 || x>=rows || y<0 || y>=cols || visited[x][y])             return 0;         visited[x][y] = true;         int res1 = 1;         int res2 = 1;         int res3=1;         int res4=1;         if(x+1<rows && matrix[x+1][y] > matrix[x][y])             res1+=helper(matrix,rows,cols,x+1,y,visited);         if(x-1>=0 && matrix[x-1][y] > matrix[x][y])             res2+=helper(matrix,rows,cols,x-1,y,visited);         if(y+1<cols && matrix[x][y+1] > matrix[x][y])             res3+=helper(matrix,rows,cols,x,y+1,visited);         if(y-1>=0 && matrix[x][y-1] > matrix[x][y])             res4+=helper(matrix,rows,cols,x,y-1,visited);         visited[x][y] = false;         return Math.max(Math.max(res1, res2), Math.max(res3, res4));     }               public static void main(String[] args){         Scanner in = new Scanner(System.in);         int res;              int _matrix_rows = 0;         int _matrix_cols = 0;         _matrix_rows = Integer.parseInt(in.nextLine().trim());         _matrix_cols = Integer.parseInt(in.nextLine().trim());                  int[][] _matrix = new int[_matrix_rows][_matrix_cols];         for(int _matrix_i=0; _matrix_i<_matrix_rows; _matrix_i++) {             for(int _matrix_j=0; _matrix_j<_matrix_cols; _matrix_j++) {                 _matrix[_matrix_i][_matrix_j] = in.nextInt();                              }         }                  if(in.hasNextLine()) {           in.nextLine();         }            res = longpath(_matrix);         System.out.println(String.valueOf(res));         } }
点赞 回复 分享
发布于 2019-04-24 20:51
def solution(): m = int(input()) n = int(input()) _matrix = [] for _ in range(m): mat_temp = list(map(int, input().split())) _matrix.append(mat_temp)   def dfs(matrix, rows, cols, i, j, cur_num):   if i < 0 or i >= rows or j < 0 or j >= cols: # 越界 return 0 if visited[i * n + j]: # 已访问 return 0 if matrix[i][j] <= cur_num: # 非递增 return 0 visited[i * cols + j] = True num = 1 + max(dfs(matrix, rows, cols, i + 1, j, matrix[i][j]), \ dfs(matrix, rows, cols, i, j + 1, matrix[i][j]), \ dfs(matrix, rows, cols, i - 1, j, matrix[i][j],), \ dfs(matrix, rows, cols, i, j - 1, matrix[i][j],)) return num max_val = 0   for i in range(m): for j in range(n): visited = [False for _ in range(m * n)]   k = dfs(_matrix, m, n, i, j, float('-INF')) max_val = max(max_val,k) return max_val res = solution() print(res)
点赞 回复 分享
发布于 2019-04-24 20:52

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务