Please use JAVA to solve this question, Thanks!!

3. Sliding Othello ALL Description On an nxm chessboard (where m is even), there are some chess pieces on each grid. Some pieces are black, and some pieces are white. There is one and only one grid on the chessboard without chess pieces. At each step, we can select a chess piece and move it to an empty grid next to it. 1 2 3 Question How many times do you need to move the chess pieces at least to move all the black chess pieces to the left half of the chessboard and all the white chess pieces to the right half of the chessboard? If the above goal cannot be achieved regardless of whether the piece is moved within 15 times (including 15 times), please output - 1. 415 left 41 seconds left H ALL 1 2 3 Input There are two numbers in the first line, n and m, which represent the height and width of the chessboard. Next, there are n rows, each with m characters. The characters in the i-th row and j-th column represent the state of the chess pieces in the i-th row and j-th column on the chessboard, where 1 means that there are black pieces, and 2 means that there are white pieces. O means there are no pieces. Output Output a number, indicating the minimum number of steps required. If it cannot be resolved within 15 steps or less, -1 will be output. Sample Input 44 1122 1101 1222 1122 22 21 21 Sample Output 6 Sample Output 6 -1 Data range For 30% of the data, n,m