Breadth-First Search
Array
Matrix
Description
On an 2 x 3
board, there are five tiles labeled from 1
to 5
, and an empty square represented by 0
. A move consists of choosing 0
and a 4-directionally adjacent number and swapping it.
The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]]
.
Given the puzzle board board
, return the least number of moves required so that the state of the board is solved . If it is impossible for the state of the board to be solved, return -1
.
Example 1:
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Explanation: Swap the 0 and the 5 in one move.
Example 2:
Input: board = [[1,2,3],[5,4,0]]
Output: -1
Explanation: No number of moves will make the board solved.
Example 3:
Input: board = [[4,1,2],[5,0,3]]
Output: 5
Explanation: 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]
Constraints:
board.length == 2
board[i].length == 3
0 <= board[i][j] <= 5
Each value board[i][j]
is unique .
Solutions
Solution 1
Python3 Java C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 class Solution :
def slidingPuzzle ( self , board : List [ List [ int ]]) -> int :
t = [ None ] * 6
def gets ():
for i in range ( 2 ):
for j in range ( 3 ):
t [ i * 3 + j ] = str ( board [ i ][ j ])
return '' . join ( t )
def setb ( s ):
for i in range ( 2 ):
for j in range ( 3 ):
board [ i ][ j ] = int ( s [ i * 3 + j ])
def f ():
res = []
i , j = next (( i , j ) for i in range ( 2 ) for j in range ( 3 ) if board [ i ][ j ] == 0 )
for a , b in [[ 0 , - 1 ], [ 0 , 1 ], [ 1 , 0 ], [ - 1 , 0 ]]:
x , y = i + a , j + b
if 0 <= x < 2 and 0 <= y < 3 :
board [ i ][ j ], board [ x ][ y ] = board [ x ][ y ], board [ i ][ j ]
res . append ( gets ())
board [ i ][ j ], board [ x ][ y ] = board [ x ][ y ], board [ i ][ j ]
return res
start = gets ()
end = "123450"
if start == end :
return 0
vis = { start }
q = deque ([( start )])
ans = 0
while q :
ans += 1
for _ in range ( len ( q )):
x = q . popleft ()
setb ( x )
for y in f ():
if y == end :
return ans
if y not in vis :
vis . add ( y )
q . append ( y )
return - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86 class Solution {
private String [] t = new String [ 6 ] ;
private int [][] board ;
public int slidingPuzzle ( int [][] board ) {
this . board = board ;
String start = gets ();
String end = "123450" ;
if ( end . equals ( start )) {
return 0 ;
}
Set < String > vis = new HashSet <> ();
Deque < String > q = new ArrayDeque <> ();
q . offer ( start );
vis . add ( start );
int ans = 0 ;
while ( ! q . isEmpty ()) {
++ ans ;
for ( int n = q . size (); n > 0 ; -- n ) {
String x = q . poll ();
setb ( x );
for ( String y : next ()) {
if ( y . equals ( end )) {
return ans ;
}
if ( ! vis . contains ( y )) {
vis . add ( y );
q . offer ( y );
}
}
}
}
return - 1 ;
}
private String gets () {
for ( int i = 0 ; i < 2 ; ++ i ) {
for ( int j = 0 ; j < 3 ; ++ j ) {
t [ i * 3 + j ] = String . valueOf ( board [ i ][ j ] );
}
}
return String . join ( "" , t );
}
private void setb ( String s ) {
for ( int i = 0 ; i < 2 ; ++ i ) {
for ( int j = 0 ; j < 3 ; ++ j ) {
board [ i ][ j ] = s . charAt ( i * 3 + j ) - '0' ;
}
}
}
private int [] find0 () {
for ( int i = 0 ; i < 2 ; ++ i ) {
for ( int j = 0 ; j < 3 ; ++ j ) {
if ( board [ i ][ j ] == 0 ) {
return new int [] { i , j };
}
}
}
return new int [] { 0 , 0 };
}
private List < String > next () {
int [] p = find0 ();
int i = p [ 0 ] , j = p [ 1 ] ;
int [] dirs = { - 1 , 0 , 1 , 0 , - 1 };
List < String > res = new ArrayList <> ();
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = i + dirs [ k ] ;
int y = j + dirs [ k + 1 ] ;
if ( x >= 0 && x < 2 && y >= 0 && y < 3 ) {
swap ( i , j , x , y );
res . add ( gets ());
swap ( i , j , x , y );
}
}
return res ;
}
private void swap ( int i , int j , int x , int y ) {
int t = board [ i ][ j ] ;
board [ i ][ j ] = board [ x ][ y ] ;
board [ x ][ y ] = t ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72 class Solution {
public :
int slidingPuzzle ( vector < vector < int >>& board ) {
string start = gets ( board );
string end = "123450" ;
if ( start == end ) return 0 ;
unordered_set < string > vis ;
vis . insert ( start );
queue < string > q {{ start }};
int ans = 0 ;
while ( ! q . empty ()) {
++ ans ;
for ( int n = q . size (); n > 0 ; -- n ) {
string x = q . front ();
q . pop ();
setb ( x , board );
for ( string y : next ( board )) {
if ( y == end ) return ans ;
if ( ! vis . count ( y )) {
vis . insert ( y );
q . push ( y );
}
}
}
}
return -1 ;
}
string gets ( vector < vector < int >>& board ) {
string s = "" ;
for ( int i = 0 ; i < 2 ; ++ i )
for ( int j = 0 ; j < 3 ; ++ j )
s . push_back ( '0' + board [ i ][ j ]);
return s ;
}
void setb ( string s , vector < vector < int >>& board ) {
for ( int i = 0 ; i < 2 ; ++ i )
for ( int j = 0 ; j < 3 ; ++ j )
board [ i ][ j ] = s [ i * 3 + j ] - '0' ;
}
vector < string > next ( vector < vector < int >>& board ) {
vector < string > res ;
auto p = find0 ( board );
int i = p . first , j = p . second ;
vector < int > dirs = { -1 , 0 , 1 , 0 , -1 };
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = i + dirs [ k ], y = j + dirs [ k + 1 ];
if ( x >= 0 && x < 2 && y >= 0 && y < 3 ) {
swap ( i , j , x , y , board );
res . push_back ( gets ( board ));
swap ( i , j , x , y , board );
}
}
return res ;
}
void swap ( int i , int j , int x , int y , vector < vector < int >>& board ) {
int t = board [ i ][ j ];
board [ i ][ j ] = board [ x ][ y ];
board [ x ][ y ] = t ;
}
pair < int , int > find0 ( vector < vector < int >>& board ) {
for ( int i = 0 ; i < 2 ; ++ i )
for ( int j = 0 ; j < 3 ; ++ j )
if ( board [ i ][ j ] == 0 )
return { i , j };
return { 0 , 0 };
}
};
Solution 2
Python3 Java C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 class Solution :
def slidingPuzzle ( self , board : List [ List [ int ]]) -> int :
m , n = 2 , 3
seq = []
start , end = '' , '123450'
for i in range ( m ):
for j in range ( n ):
if board [ i ][ j ] != 0 :
seq . append ( board [ i ][ j ])
start += str ( board [ i ][ j ])
def check ( seq ):
n = len ( seq )
cnt = sum ( seq [ i ] > seq [ j ] for i in range ( n ) for j in range ( i , n ))
return cnt % 2 == 0
def f ( s ):
ans = 0
for i in range ( m * n ):
if s [ i ] != '0' :
num = ord ( s [ i ]) - ord ( '1' )
ans += abs ( i // n - num // n ) + abs ( i % n - num % n )
return ans
if not check ( seq ):
return - 1
q = [( f ( start ), start )]
dist = { start : 0 }
while q :
_ , state = heappop ( q )
if state == end :
return dist [ state ]
p1 = state . index ( '0' )
i , j = p1 // n , p1 % n
s = list ( state )
for a , b in [[ 0 , - 1 ], [ 0 , 1 ], [ 1 , 0 ], [ - 1 , 0 ]]:
x , y = i + a , j + b
if 0 <= x < m and 0 <= y < n :
p2 = x * n + y
s [ p1 ], s [ p2 ] = s [ p2 ], s [ p1 ]
next = '' . join ( s )
s [ p1 ], s [ p2 ] = s [ p2 ], s [ p1 ]
if next not in dist or dist [ next ] > dist [ state ] + 1 :
dist [ next ] = dist [ state ] + 1
heappush ( q , ( dist [ next ] + f ( next ), next ))
return - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 class Solution {
private int m = 2 ;
private int n = 3 ;
public int slidingPuzzle ( int [][] board ) {
String start = "" ;
String end = "123450" ;
String seq = "" ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
start += board [ i ][ j ] ;
if ( board [ i ][ j ] != 0 ) {
seq += board [ i ][ j ] ;
}
}
}
if ( ! check ( seq )) {
return - 1 ;
}
PriorityQueue < Pair < Integer , String >> q
= new PriorityQueue <> ( Comparator . comparingInt ( Pair :: getKey ));
Map < String , Integer > dist = new HashMap <> ();
dist . put ( start , 0 );
q . offer ( new Pair <> ( f ( start ), start ));
int [] dirs = { - 1 , 0 , 1 , 0 , - 1 };
while ( ! q . isEmpty ()) {
String state = q . poll (). getValue ();
int step = dist . get ( state );
if ( end . equals ( state )) {
return step ;
}
int p1 = state . indexOf ( "0" );
int i = p1 / n , j = p1 % n ;
char [] s = state . toCharArray ();
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = i + dirs [ k ] , y = j + dirs [ k + 1 ] ;
if ( x >= 0 && x < m && y >= 0 && y < n ) {
int p2 = x * n + y ;
swap ( s , p1 , p2 );
String next = String . valueOf ( s );
if ( ! dist . containsKey ( next ) || dist . get ( next ) > step + 1 ) {
dist . put ( next , step + 1 );
q . offer ( new Pair <> ( step + 1 + f ( next ), next ));
}
swap ( s , p1 , p2 );
}
}
}
return - 1 ;
}
private void swap ( char [] arr , int i , int j ) {
char t = arr [ i ] ;
arr [ i ] = arr [ j ] ;
arr [ j ] = t ;
}
private int f ( String s ) {
int ans = 0 ;
for ( int i = 0 ; i < m * n ; ++ i ) {
if ( s . charAt ( i ) != '0' ) {
int num = s . charAt ( i ) - '1' ;
ans += Math . abs ( i / n - num / n ) + Math . abs ( i % n - num % n );
}
}
return ans ;
}
private boolean check ( String s ) {
int n = s . length ();
int cnt = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = i + 1 ; j < n ; ++ j ) {
if ( s . charAt ( i ) > s . charAt ( j )) {
++ cnt ;
}
}
}
return cnt % 2 == 0 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 class Solution {
public :
int m = 2 ;
int n = 3 ;
int slidingPuzzle ( vector < vector < int >>& board ) {
string start , seq ;
string end = "123450" ;
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < n ; ++ j ) {
start += char ( board [ i ][ j ] + '0' );
if ( board [ i ][ j ] != 0 ) seq += char ( board [ i ][ j ] + '0' );
}
}
if ( ! check ( seq )) return -1 ;
typedef pair < int , string > PIS ;
priority_queue < PIS , vector < PIS > , greater < PIS >> q ;
unordered_map < string , int > dist ;
dist [ start ] = 0 ;
q . push ({ f ( start ), start });
vector < int > dirs = { -1 , 0 , 1 , 0 , -1 };
while ( ! q . empty ()) {
PIS t = q . top ();
q . pop ();
string state = t . second ;
int step = dist [ state ];
if ( state == end ) return step ;
int p1 = state . find ( '0' );
int i = p1 / n , j = p1 % n ;
for ( int k = 0 ; k < 4 ; ++ k ) {
int x = i + dirs [ k ], y = j + dirs [ k + 1 ];
if ( x < 0 || x >= m || y < 0 || y >= n ) continue ;
int p2 = x * n + y ;
swap ( state [ p1 ], state [ p2 ]);
if ( ! dist . count ( state ) || dist [ state ] > step + 1 ) {
dist [ state ] = step + 1 ;
q . push ({ step + 1 + f ( state ), state });
}
swap ( state [ p1 ], state [ p2 ]);
}
}
return -1 ;
}
bool check ( string s ) {
int n = s . size ();
int cnt = 0 ;
for ( int i = 0 ; i < n ; ++ i )
for ( int j = i ; j < n ; ++ j )
if ( s [ i ] > s [ j ])
++ cnt ;
return cnt % 2 == 0 ;
}
int f ( string s ) {
int ans = 0 ;
for ( int i = 0 ; i < m * n ; ++ i ) {
if ( s [ i ] == '0' ) continue ;
int num = s [ i ] - '1' ;
ans += abs ( num / n - i / n ) + abs ( num % n - i % n );
}
return ans ;
}
};
GitHub