| ||||||||||
| 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 Solution
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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator