Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Simple Java Solution

Posted by bjarison at 2021-09-27 23:50:06 on Problem 1088
public 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator