UVA - 10913 - Walking on a Grid

This article will explain my thought process to solve a problem called Walking on a Grid (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Graph, Directed Acyclic Graph, Dynamic Programming

Problem Summary

Given:

Size of a square grid.
Value of each square.
Maximum allowed negative squares.
Origin square (top-left).
Destination square (bottom-right).

We want to:

Determine whether it is possible to reach the destination square from the origin square.
Find the maximum sum of square values from such a path.

Glossary

Graph — A structure consisting of a set of objects where some pairs of the objects are related.
Directed Acyclic Graph (DAG) — A directed graph with no directed cycles.
Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.

Observation

The relationship between the grid’s squares and the walks (left/right/down) can be modeled as a graph, where the squares are the vertices and the walk directions are the edges. Since each squares has its own values, the graph can be classified as a weighted graph where the square’s values are the weighted edges. Since we are traveling one-way from top to bottom and it is impossible to walk up, the graph could be classified as a DAG.

DAG problem can also be represented as a DP problem by transforming the vertices as the sub-problems and the edges as the transition between sub-problems. In this case, we could define the sub-problems as finding the maximum sum to reach each square from the first row until the last row. We are iteratively finding the maximum sum from the first to last row, so the row levels became the transition edges.

Since there is 3 possible directions (left/right/down) and we are only allowed to visit the square once, it is impossible for us to take a right immediately after a left, and vice-versa. In other words, only 7 combinations of directions are possible: down + right, right + right, down + left, left + left, down + down, left + down, right + down. For each row level, we tried the 7 combinations of walk while keeping track of the maximum sum to reach each square.

In addition to the 7 walk combinations, we also need to take into account for the total negative squares. This can be achieved by trying every possible total negative squares on top of the existing combinations. To avoid re-computation, the maximum sum are stored in a 4 dimension DP table (walk directions, total negative squares, rows, columns).

Algorithm

The DP can be implemented using bottom-up approach. This means, we are using tabulation to store the result of the calculation and iteratively compute the maximum sum from the base case (row = 0, column = 0) until the final case (row = grid size - 1, column = grid size - 1).

After the DP is completed, we’ll have the maximum sum to reach every squares based on every possible total negative squares and every possible last direction taken by us. We just need to extract the maximum sum on the bottom-right square to get the answer.

The time complexity of this solution is O({total directions} * {total negatives} * {grid size} * {grid size}) or O(10^4).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 10913 - Walking on a Grid
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1854
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        for (int caseId = 1; in.hasNextInt(); caseId++) {
            final Input input = new Input();
            input.caseId = caseId;
            input.gridSize = in.nextInt();
            input.negativeCount = in.nextInt();
            if (input.isEOF()) break;

            input.grid = new int[input.gridSize][input.gridSize];
            for (int i = 0; i < input.gridSize; i++) {
                for (int j = 0; j < input.gridSize; j++) {
                    input.grid[i][j] = in.nextInt();
                }
            }

            final Output output = process.process(input);
            if (output.isPossible) {
                out.format("Case %d: %d\n", output.caseId, output.sum);
            } else {
                out.format("Case %d: impossible\n", output.caseId);
            }
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int caseId;
    public int gridSize;
    public int negativeCount;
    public int[][] grid;

    public boolean isEOF() {
        return gridSize == 0 && negativeCount == 0;
    }
}

class Output {
    public int caseId;
    public boolean isPossible;
    public int sum;
}

class Process {
    private static final int DOWN = 0;
    private static final int LEFT = 1;
    private static final int RIGHT = 2;

    public Output process(final Input input) {
        final Output output = new Output();
        output.caseId = input.caseId;
        output.sum = Integer.MIN_VALUE;

        final int[][][][] totals = new int[3][input.negativeCount + 1][input.gridSize][input.gridSize];
        fill(totals, Integer.MIN_VALUE);

        final int startValue = input.grid[0][0];
        final int startTotalNegatives = startValue < 0 ? 1 : 0;
        totals[DOWN][startTotalNegatives][0][0] = startValue;

        for (int count = 0; count <= input.negativeCount; count++) {
            for (int row = 0; row < input.gridSize; row++) {
                // (DOWN/RIGHT) + RIGHT
                for (int direction : new int[]{DOWN, RIGHT}) {
                    for (int col = 0; col < input.gridSize - 1; col++) {
                        final int sum = totals[direction][count][row][col];
                        final int rightCol = col + 1;
                        final int rightVal = input.grid[row][rightCol];
                        final int rightSum = sum + rightVal;
                        final int rightCount = count + (rightVal < 0 ? 1 : 0);

                        if (sum == Integer.MIN_VALUE) continue;
                        if (rightCount > input.negativeCount) continue;

                        totals[RIGHT][rightCount][row][rightCol] = Math.max(
                            totals[RIGHT][rightCount][row][rightCol],
                            rightSum
                        );
                    }
                }

                // (DOWN/LEFT) + LEFT
                for (int direction : new int[]{DOWN, LEFT}) {
                    for (int col = input.gridSize - 1; col > 0; col--) {
                        final int sum = totals[direction][count][row][col];
                        final int leftCol = col - 1;
                        final int leftVal = input.grid[row][leftCol];
                        final int leftSum = sum + leftVal;
                        final int leftCount = count + (leftVal < 0 ? 1 : 0);

                        if (sum == Integer.MIN_VALUE) continue;
                        if (leftCount > input.negativeCount) continue;

                        totals[LEFT][leftCount][row][leftCol] = Math.max(
                            totals[LEFT][leftCount][row][leftCol],
                            leftSum
                        );
                    }
                }

                // (DOWN/LEFT/RIGHT) + DOWN
                if (row == input.gridSize - 1) continue;
                for (int direction : new int[]{DOWN, LEFT, RIGHT}) {
                    for (int col = 0; col < input.gridSize; col++) {
                        final int sum = totals[direction][count][row][col];
                        final int downRow = row + 1;
                        final int downVal = input.grid[downRow][col];
                        final int downSum = sum + downVal;
                        final int downCount = count + (downVal < 0 ? 1 : 0);

                        if (sum == Integer.MIN_VALUE) continue;
                        if (downCount > input.negativeCount) continue;

                        totals[DOWN][downCount][downRow][col] = Math.max(
                            totals[DOWN][downCount][downRow][col],
                            downSum
                        );
                    }
                }

            }
        }

        for (int count = 0; count <= input.negativeCount; count++) {
            for (int direction : new int[]{DOWN, LEFT, RIGHT}) {
                final int total = totals[direction][count][input.gridSize - 1][input.gridSize - 1];
                output.sum = Math.max(output.sum, total);
            }
        }
        output.isPossible = output.sum > Integer.MIN_VALUE;

        return output;
    }

    private void fill(final int[][][][] array, final int value) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                for (int k = 0; k < array[i][j].length; k++) {
                    for (int l = 0; l < array[i][j][k].length; l++) {
                        array[i][j][k][l] = value;
                    }
                }
            }
        }
    }
}