import java.awt.Point; import java.io.PrintStream; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Scanner; /** * Solution to Snake * * @author vanb */ public class snake_vanb { /** Input. */ private static Scanner sc; /** Output. */ private static PrintStream ps; /** A State of a BFS */ private class State { // Location (i,j) and # of steps to get there public int i, j, steps; public State(int i, int j, int steps) { super(); this.i = i; this.j = j; this.steps = steps; } } private char grid[][]; private boolean visited[][]; private int r, c, tail=0; private ArrayDeque q; private boolean solvable = false; /** * Convert a character to a hex value * * @param ch A character, 0-9 or a-f * @return Hex value */ private int hex( char ch ) { return Character.isDigit( ch ) ? ch-'0' : 10+ch-'a'; } /** * Perform a move in the BFS, *IF* valid * * @param i Row * @param j Column * @param steps Number of steps */ private void move( int i, int j, int steps ) { if( i>=0 && i=0 && j=0 && i=0 && jtail-hex(ch) ) { solvable = true; } } } /** * Do it! */ private void doit() { r = sc.nextInt(); c = sc.nextInt(); grid = new char[r][c]; visited = new boolean[r][c]; for( int i=0; itail ) { tail = hex(ch); } } q = new ArrayDeque(r*c); move( headi+1, headj, 1 ); move( headi-1, headj, 1 ); move( headi, headj+1, 1 ); move( headi, headj-1, 1 ); while( !q.isEmpty() && !solvable ) { State s = q.poll(); char ch = grid[s.i][s.j]; if( ch=='.' ) { move( s.i-1, s.j, s.steps+1 ); move( s.i+1, s.j, s.steps+1 ); move( s.i, s.j-1, s.steps+1 ); move( s.i, s.j+1, s.steps+1 ); } else if( ch=='A' ) solvable = true; else if( r>1 && c>1 && (s.steps>tail-hex(ch) || hex(ch)==tail ) ) solvable = true; } if( !solvable && r>1 && c>1 ) { plumber( headi+1, headj, 1 ); plumber( headi-1, headj, 1 ); plumber( headi, headj+1, 1 ); plumber( headi, headj-1, 1 ); } ps.println( solvable ? 1 : 0 ); } /** * Main. * * @param args unused * @throws Exception */ public static void main( String[] args ) throws Exception { sc = new Scanner( System.in ); ps = System.out; new snake_vanb().doit(); } }