<style>
html, body, .ui-content {
background-image: url(https://truth.bahamut.com.tw/s01/201508/7f0e4bd0e01135c9df434733e0d1544a.JPG);
background-color: #333;
color: #DDD;
}
</style>

###### tags: `Meowmeow Online Judge`

# Swap Game

## Description
You are given a 3 x 3 grid containing the numbers 1, 2, ..., 9. Your task is to perform a sequence of moves so that the grid will look like this:

1 2 3

3 4 5

7 8 9

On each move, you can swap the numbers in any two adjacent squares(horizontally or vertically). What is the minimum number of moves required?

## Input
The input has three lines, and each of them has three integers.

## Output
Print one integer: the minimum number of moves.

## 解題思路
盤面最多只會有 $9!$ 種可能，所以可以用BFS加上unordered_set來解題
使用string而不是vector是因為unordered_map比較好處理

## Code

#include <iostream>
#include <set>
#include <vector>
#include <deque>
#include <utility>
#include <algorithm>
#include <unordered_set>

int main() {
    const std::string target = {"0123456789"};
    std::string grid =         {"0000000000"};

    for (int i = 1; i <= 9; i++) std::cin >> grid[i];

    std::deque<std::pair<std::string, int>> dq; // grid and number of moves
    std::unordered_set<std::string> st;

    dq.emplace_back(grid, 0);
    st.insert(grid);
    while (!dq.empty()) {
        if (dq.front().first == target) {
            std::cout << dq.front().second << std::endl;
            break;
        }
        for (int i = 1; i <= 9; i++) {
            // swap left and right
            if (i % 3 != 0) {
                auto new_grid = dq.front().first;
                std::swap(new_grid[i], new_grid[i + 1]);
                if (!st.count(new_grid)) {
                    dq.emplace_back(new_grid, dq.front().second + 1);
                    st.insert(new_grid);
                }
            }
            // swap up and down
            if (i <= 6) {
                auto new_grid = dq.front().first;
                std::swap(new_grid[i], new_grid[i + 3]);
                if (!st.count(new_grid)) {
                    dq.emplace_back(new_grid, dq.front().second + 1);
                    st.insert(new_grid);
                }
            } 
        }
        dq.pop_front();
    }
    if (dq.empty()) std::cout << "No solution" << std::endl;
    return 0;
}