New update is available. Click here to update.

Last Updated: 23 Mar, 2021

Difficulty: Hard

```
Board will be a 2 x 3 array as described above.
BOARD[i][j] will be a permutation of [0, 1, 2, 3, 4, 5].
```

```
Given ‘BOARD’ = [[1,2,0],[4,5,3]]
The answer here would be one since we only need to swap 0 and 3, and we will have the required configuration.
```

```
The first line of input contains an integer T denoting the number of test cases.
The following 2*T lines of each test case contain the ‘BOARD’, where each line has exactly three space-separated integers.
```

```
For each test case, print a single line containing a single integer denoting the minimum number of swaps for the given board.
The output of each test case will be printed in a separate line.
```

```
You don't have to print anything. It has been already taken care of. Just implement the given function.
```

```
1 <= T <= 50
0 <= BOARD[i][j] <= 5
Where ‘T’ is the total number of test cases, and ‘BOARD’ matrix and ‘BOARD’[i][j] is the value of pairs (i,j).
Time limit: 1 sec.
```

The main idea is to do all the possible swaps we can do, and if we find the required configuration, we return the number of moves we made to get to this state.If we ever encounter a state we have already encountered, we can skip that state.

- Make a queue(que) which, for each state, stores the number of moves we have made till now and also the current state of the board.

- Maintain a hashmap(mp) that stores all the states that we have previously encountered.

- If we come to a state we have not encountered before, we make the swap and then push it in the que.

- If at any point we get the required board, we return the number of moves we have made till now.

- If we never encounter the required board, we return -1.

SIMILAR PROBLEMS

Is Graph Bipartite?

Posted: 28 Jan, 2022

Difficulty: Moderate

Valid Arrangement of Pairs

Posted: 28 Jan, 2022

Difficulty: Hard

Valid Arrangement of Pairs

Posted: 28 Jan, 2022

Difficulty: Hard

Valid Arrangement of Pairs

Posted: 28 Jan, 2022

Difficulty: Hard

Left Right Print

Posted: 9 Jul, 2022

Difficulty: Moderate

The Summit

Posted: 15 Sep, 2022

Difficulty: Easy

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: