# How can I optimize this Java 2D Array BFS?

This is a Google foobar question. The gist of it is that I have to find the shortest path from top left to bottom right in a 2d array of 1's and 0's, where I can only traverse on 0's. However, the twist is that I can change one 1 to a 0. My code works for the first three test cases, but it fails the final two (not sure if it's an edge case or it's pure inefficiency).

My current solution is to test every possible array (switch every possible 1 to a 0) and then run BFS on each one.

How can I optimize my code further? Thanks! If you want, here's the full text of the problem.

import java.lang.Integer;
import java.lang.String;
import java.util.Arrays;
import java.lang.Math;
import java.util.Queue;

public class Solution {

public static void main (String[] args)
{
int[][]x = {{0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 0, 0}, {1, 1, 1, 0}};
System.out.println(solution(x));
}

public static int solution(int[][] map) {
int w = map[0].length;
int h = map.length;
if(w==1&h==1)
return 1;
int[][] m = map;
int min = minPath(m,w,h);
//System.out.println(min);
for (int i = 0; i<w; i++)
{
for (int j = 0; j<h;j++)
{
if(m[j][i]==1)
{
m[j][i] = 0;
min = Math.min(min, minPath(m,w,h));
if(min==w+h-1)
return min;
m[j][i] = 1;
}

}
}
return min;
}

public static int minPath(int[][]m, int w, int h)
{
int[][] d = new int[h][w];
d[0][0] = 1;

while(!q.isEmpty())
{
String x = q.remove();
int i = Integer.parseInt(x.split(",")[0]);
int j = Integer.parseInt(x.split(",")[1]);
if (i==h-2&&j==w-1 || i==h-1&&j==w-2)
return ++d[i][j];
if(i>1&&d[i-1][j]==0&&m[i-1][j]==0)
{
d[i-1][j] = d[i][j] + 1;
}
if(j>1&&d[i][j-1]==0&&m[i][j-1]==0)
{
d[i][j-1] = d[i][j] + 1;
}
if(i<h-1&&d[i+1][j]==0&&m[i+1][j]==0)
{
d[i+1][j] = d[i][j] + 1;
}
if(j<w-1&&d[i][j+1]==0&&m[i][j+1]==0)
{
d[i][j+1] = d[i][j] + 1;