773. Sliding Puzzle

BFS - grid data convert to String format

/*
grid convert to String format:
ex: 

[[1,2,3],[4,5,0]]. => 123450

[[1,2,3],[4,0,5]]. => 123405

use bfs, find  least number of moves 
=> change 4 direction, 

[[1,2,3],
[4,0,5]]. => when 5 swap with 0 => achieve 123450


if can achieve 123450 => return steps

*/

2*3 = 6, 6! permutation of the 6 numbers,

T: O(mn + mn*(mn!)),

S:O(mn + mn!)

class Solution {
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    public int slidingPuzzle(int[][] board) {
        String s = "";
        for (int i = 0 ; i < board.length; i++) { // transform to String format, inorder to check result easier
            for (int j = 0; j < board[0].length; j++) {
                s += board[i][j];
            }
        }
        if ("123450".equals(s)) { //find ans
            return 0;
        }
        
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new ArrayDeque<>();
        queue.offer(s);
        visited.add(s);
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                
                if ("123450".equals(curr)) { //find ans
                    return steps;
                }
                
                int index = curr.indexOf('0'); // find '0' index , easier!
                
                int x = index/3; // String index to x, y index
                int y = index%3;
                for (int dir[] : dirs) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];
                    
                    if (!inArea(board, newX, newY)) {
                        continue;
                    }
                    int newIndex = newX*3 + newY; // new String index
                    String newString = swap(curr, index, newIndex); // get new String
                    if (visited.contains(newString)) {
                        continue;
                    }
                    queue.offer(newString);
                    visited.add(newString);
                }
            }
            steps++;
        }
        
        return -1;
    }
    private boolean inArea(int[][] board, int i, int j) {
        return (i >= 0 && i < board.length && j >= 0 && j < board[0].length);
    }
    
    private String swap(String s, int i, int j) {
        char[] charArray = s.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }
    // or direct change
    // private String swap(String s, int index, int newIndex) {
    //     char[] charArray = s.toCharArray();
    //     charArray[index] = charArray[newIndex];
    //     charArray[newIndex] = '0';
    //     return String.valueOf(charArray);
    // }
}

//  6! permutation of the 6 numbers, 2*3 = 6
// T: O(mn + mn*(mn!)), S:O(mn + mn!)
// do dfs

// encode board to String

// 123450

// bfs from 0
// so find 0's index, 
    
// bfs from 0 for 4 directions, visited<String> to store visited

// if (string == '123450') return steps

pre calculate the swap position && new style BFS

key:

1. how to define the final state? in[][] to String

2. how to define the move?

visited use Set<String>, for certain String pattern, we have visited...

```java
class Solution {
    class Step {
        String state;
        int emptyIndex;
        int count;
        Step(String state, int emptyIndex, int count) {
            this.state = state;
            this.emptyIndex = emptyIndex;
            this.count = count;
        }
    }
    public int slidingPuzzle(int[][] board) {
        // empty place's neightbor, we can use to swap later
        int[][] swap = {{1,3},{0,4,2},{1,5},{0,4},{1,3,5},{2,4}};
        StringBuilder state = new StringBuilder();
        int k = 0;
        int emptyIndex = -1;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 0) {
                    emptyIndex = k;
                }
                state.append(board[i][j]);
                k++;
            }
        }
        Set<String> visited = new HashSet<>();
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(state.toString(), emptyIndex, 0));

        while (!queue.isEmpty()) {
            Step cur = queue.poll();

            if (visited.contains(cur.state)) {
                continue;
            }
            if ("123450".equals(cur.state)) {
                return cur.count;
            }
            visited.add(cur.state);
            for (int position : swap[cur.emptyIndex]) {
                String nextStr = swap(cur.state, position, cur.emptyIndex);
                queue.offer(new Step(nextStr, position, cur.count+1));
            }
        }
        return -1;
    }
    private String swap(String s, int i, int j) {
        char[] c = s.toCharArray();
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;
        return String.valueOf(c);
    }
}
/*

0 1 2
3 4 5 -> 0 1 2 3 4 5

{1,3}
{0,4,2}
{1,5}
{0,4}
{1,3,5}
{2,4}




*/
```