Inverted cells

You are given a matrix $n\ast m$. The matrix rows are numbered from $1$ to $n$ from top to bottom and the matrix columns are numbered from $1$ to $m$ from left to right. The cells of the field at the intersection of the $x^{th}$ row and the $y^{th}$column has coordinates $(x,y)$.

Every cell is empty or blocked. For every cell $(x,y)$, determine if you change the state of cell $(x,y)$(empty to blocked or blocked to empty), then is it possible to reach cell $(n,m)$ from $(1,1)$ by going only down and right.

Input format

Example:

Input : 
5 5
..#..
#...#
#...#
....#
.##..
Output:
0 0 1 1 1 
1 0 1 1 1 
1 1 1 1 1 
1 1 1 0 1 
1 1 1 0 0 

Approach

Java

import java.io.BufferedReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class InvertedCells {
    static int n, m;
    static char[][] g;
    static boolean[][] art, dp1, dp2;
    static int time = 0;
    static int rooti = 0, rootj = 0;
    static int rootChildren = 0;
    static int[][] start, low, state;
    static int[][] parent;

    public static void main(String[] args) {
        n = 5;
        m = 5;

        char arr[][] = { { '.', '.', '#', '.', '.' }, { '#', '.', '.', '.', '#' }, { '#', '.', '.', '.', '#' },
                { '.', '.', '.', '.', '#' }, { '.', '#', '#', '.', '.' } };

        g = new char[n][m];
        for (int i = 0; i < n; i++) {
            g[i] = arr[i];
        }

        dp1 = new boolean[n][m];
        dp1[0][0] = true;

        dp2 = new boolean[n][m];
        dp2[n - 1][m - 1] = true;

        art = new boolean[n][m];

        int[][] next = { { 0, 1 }, { 1, 0 } };
        int[][] prev = { { 0, -1 }, { -1, 0 } };

        dp1(next, dp1);
        dp2(prev, dp2);

        if (!dp1[n - 1][m - 1]) {
            // not reachable
            for (int i = 0; i < n; i++) {
                Arrays.fill(art[i], true);
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (g[i][j] == '.')
                        continue;
                    for (int a = 0; a < 2; a++) {
                        for (int b = 0; b < 2; b++) {
                            int previ = i + prev[a][0];
                            int prevj = j + prev[a][1];
                            int nexti = i + next[b][0];
                            int nextj = j + next[b][1];
                            if (nexti >= n || nextj >= m || nexti < 0 || nextj < 0)
                                continue;
                            if (previ >= n || prevj >= m || previ < 0 || prevj < 0)
                                continue;
                            if (dp1[previ][prevj] && dp2[nexti][nextj])
                                art[i][j] = false;
                        }
                    }
                }
            }
        } else {
            // reachable do articulation point algorithm
            start = new int[n][m];
            low = new int[n][m];
            state = new int[n][m];
            art = new boolean[n][m];
            parent = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (state[i][j] == 0 && dp1[i][j] && dp2[i][j]) {
                        rooti = i;
                        rootj = j;
                        dfs(i, j);
                        art[i][j] = rootChildren > 1;
                    }
                }
            }
            art[0][0] = true;
            art[n - 1][m - 1] = true;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (art[i][j])
                    sb.append("0");
                else
                    sb.append("1");

                if (j != m - 1)
                    sb.append(" ");
            }
            sb.append("\n");
        }

        System.out.print(sb);

    }

    public static void dp1(int[][] dir, boolean[][] dp) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!dp[i][j])
                    continue;
                if (g[i][j] == '#') {
                    dp[i][j] = false;
                    continue;
                }
                for (int k = 0; k < dir.length; k++) {
                    int[] d = dir[k];
                    int newi = i + d[0];
                    int newj = j + d[1];
                    if (newi >= n || newj >= m || newi < 0 || newj < 0)
                        continue;
                    dp[newi][newj] = true;
                }
            }
        }
    }

    public static void dp2(int[][] dir, boolean[][] dp) {
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (!dp[i][j])
                    continue;
                if (g[i][j] == '#') {
                    dp[i][j] = false;
                    continue;
                }
                for (int k = 0; k < dir.length; k++) {
                    int[] d = dir[k];
                    int newi = i + d[0];
                    int newj = j + d[1];
                    if (newi >= n || newj >= m || newi < 0 || newj < 0)
                        continue;
                    dp[newi][newj] = true;
                }
            }
        }
    }

    public static void dfs(int i, int j) {
        time++;
        start[i][j] = low[i][j] = time;
        state[i][j] = 1;

        int[][] dir = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

        for (int a = 0; a < dir.length; a++) {
            int newi = i + dir[a][0];
            int newj = j + dir[a][1];
            if (newi >= n || newj >= m || newi < 0 || newj < 0)
                continue;
            if (!(dp1[newi][newj] && dp2[newi][newj]))
                continue;
            if (state[newi][newj] == 0) {
                if (i == rooti && j == rootj)
                    rootChildren++;
                parent[newi][newj] = i * 1002 + n;
                dfs(newi, newj);
                if (low[newi][newj] >= start[i][j])
                    art[i][j] = true;
                low[i][j] = Math.min(low[i][j], low[newi][newj]);
            } else if (newi * 1002 + newj != parent[i][j])
                low[i][j] = Math.min(low[i][j], low[newi][newj]);
        }

        state[i][j] = 2;
        time++;
    }

    // print the matrix
    public static void print(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++)
                System.out.print(a[i][j] + " ");
            System.out.println("");
        }
        System.out.println("");
    }

}