TocaDois.java

package br.com.pxpc2.treino;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * OBI 2016 questao Toca do Saci
 * @author Pedro Daia
 */
public class TocaDois
{

    private static int n;
    private static int m;
    private static int[][] sala;

    private static int x;
    private static int y;
    private static int xf;
    private static int yf;
 
    private static int[] vx = {0, 1, 0, -1}; // positions to check
    private static int[] vy = {1, 0, -1, 0}; // for neighbours

    private static int[][] dist;

    public static void main(final String[] args)
    {
        final Scanner s = new Scanner(System.in);
        n = s.nextInt();
        m = s.nextInt();
        sala = new int[n][m];
        dist = new int[n][m];

        for (int nn = 0; nn < n; nn++)
        {
            for (int mm = 0; mm < m; mm++)
            {
                sala[nn][mm] = s.nextInt();
                if (sala[nn][mm] == 2)
                {
                    x= nn;
                    y = mm;
                    dist[x][y] = 1;
                }
                // set all vertices to -1 (but the initial vertex)
                else if (sala[nn][mm] == 3)
                {
                    xf = nn;
                    yf = mm;
                    dist[nn][mm] = -1;
                }
                else
                {
                    dist[nn][mm] = -1;
                }
            }
        }
        bfs(x, y);
        System.out.print(dist[xf][yf]);
    }

    /**
     *
     * @param x init coord x
     * @param y init coord y
     */
    private static void dfs(int x, int y)
    {
        for (int k = 0; k < 4; k++)
        {
            int xx = x + vx[k];
            int yy = y + vy[k];
            if (xx < n && yy < m)
            {
                if (xx >= 0 && yy >= 0) // thank you debugging
                {
                    if (dist[xx][yy] < 0 && sala[xx][yy] > 0) 
                        {
                        dist[xx][yy] = dist[x][y] + 1; 
                        dfs(xx, yy);
                    }
                }
            }
        }
    }

    private static void bfs(int x, int y)
    {
        LinkedList<Integer> qX = new LinkedList<>(); // add last, remove first for FIFO
        LinkedList<Integer> qY = new LinkedList<>();
        qX.addFirst(x);
        qY.addFirst(y);
        while (!qX.isEmpty() && !qY.isEmpty())
        {
            int xx = qX.removeFirst();
            int yy = qY.removeFirst();
            for (int k = 0; k < 4; k++)
            {
                int adjX = xx + vx[k];
                int adjY = yy + vy[k];
                if (xx < n && yy < m)
                {
                    if (dist[adjX][adjY] < 0 && sala[adjX][adjY] > 0)
                    {
                        dist[adjX][adjY] = dist[xx][yy] + 1;
                        qX.addLast(x);
                        qY.addLast(y);
                    }
                }
            }
        }
    }

}