Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Simple Java Solutionpublic class Main { int[][] memo = null; int[][] grid = null; static int dx[] = {0, -1, 0, 1}; //ruld static int dy[] = {1, 0, -1, 0}; public int dfs(int x, int y) { if (memo[x][y] > 0) { return memo[x][y]; } int maxStep = 1; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if ((nx >= 0) && (nx < grid.length) && (ny >= 0) && (ny < grid[0].length)) { if (grid[x][y] > grid[nx][ny]) { int nMaxLen = dfs(nx, ny); maxStep = Math.max(maxStep, nMaxLen + 1); } } } memo[x][y] = maxStep; return maxStep; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int r = scanner.nextInt(); int c = scanner.nextInt(); Main mn = new Main(); mn.memo = new int[r][c]; mn.grid = new int[r][c]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { int data = scanner.nextInt(); mn.grid[i][j] = data; } } int maxLen = 0; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { int curLen = mn.dfs(i, j); if (maxLen < curLen) { maxLen = curLen; } } } System.out.println(maxLen); } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator