static int[] di = { 0, 0, 1, -1 };
	static int[] dj = { 1, -1, 0, 0 };

	public int maxJumps(String[] board) {
		char[][] a = new char[board.length][board[0].length()];
		for (int i = 0; i < board.length; i++)
			a[i] = board[i].toCharArray();

		if (a[0][0] == 'H')
			return 0;

		int[][] dp = new int[a.length][a[0].length];
		boolean[][] v = new boolean[a.length][a[0].length];

		for (int[] i : dp)
			Arrays.fill(i, -1);
		dp[0][0] = 1;
		v[0][0] = true;

		int res = dfs(0, 0, dp, v, a, 1);

		return res;

	}

	private int dfs(int i, int j, int[][] dp, boolean[][] v, char[][] a, int c) {
	   int m = a[i][j] - '0';

	   int max = 1;

	   for(int d = 0; d < 4; d++){
		   int ii = i + m*di[d];
		   int jj = j + m*dj[d];

		   if(ii < 0 || ii >= a.length || jj < 0 || jj >= a[0].length){max = Math.max(max, c); continue;}
		   if(a[ii][jj] == 'H'){max = Math.max(max, c); continue;}

		   if(v[ii][jj])return -1;

		   if(c+1 > dp[ii][jj]){
			   v[ii][jj] = true;

			   dp[ii][jj] = c+1;

			   int ret = dfs(ii, jj, dp, v, a, c+1);
			   if(ret == -1)return -1;

			   max = Math.max(max, ret);

			   v[ii][jj] = false;
		   }

	   }

	   return max;
	}