Bài toán TACANH

Submit solution
Points: 3
Time limit: 1.0s
Python 3 5.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Bài toán TACANH là 1 bài toán biến đổi trên bảng số.

Trong bài này ta xét bảng số \(3*3\) điền các số khác nhau từ 0 đến 9, mỗi bước biến đổi cho phép hoán đổi số 0 với một trong 4 láng giềng sát bên nếu có.

\[\left[ \begin{matrix} 2 & 0 & 3 \\ 1 & 4 & 6 \\ 7 & 5 & 8 \\ \end{matrix} \right] \to \left[ \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 0 \\ \end{matrix} \right]\]

Nhiệm vụ của bạn là nhập vào trạng thái xuất phát và kết thúc hãy in ra số phép biến đổi ít nhất để biến đổi trạng thái xuất phát thành kết thúc, nếu bài toán không có lời giải chỉ cần xuất ra \(-1\).

Input

Gồm hai ma trận mỗi ma trận cỡ \(3*3\) cách nhau bởi một dòng trống

Output

Số phép biến đổi ít nhất

Ví dụ 1

Input

1 2 3
4 5 6
7 8 0

2 3 1
4 5 6
7 8 0

Output

16

Ví dụ 2

Input

1 2 3
4 5 6
7 8 0

2 1 3
4 5 6
7 8 0

Output

-1
tichpx

Comments


  • 2
    TICHPX  commented on Sept. 10, 2021, 9:47 a.m.

    Code tham khảo

    #include<bits/stdc++.h>
using namespace std;
typedef pair<int,string> TT;
class tacanh
{
    map<TT,int> P;
    TT s,f;
    vector<int> Next[9]={{1,3},{2,0,4},{1,5},{4,6,0},{5,3,7,1},{4,8,2},{7,3},{8,6,4},{7,5}};
    void BFS()
    {
        if(s==f) {cout<<0; return;}
        queue<TT> Q;
        Q.push(s);
        P[s]=1;
        while(Q.size())
        {
            TT u=Q.front(); Q.pop();
            if(P[u]>1000) {cout<<-1; return;}
            for(auto x:Next[u.first]) 
            {
                string s=u.second;
                swap(s[u.first],s[x]);
                TT z={x,s};
                if(P.find(z)==P.end())
                {
                    P[z]=P[u]+1;
                //  cout<<P[z]-1<<" ";
                    Q.push(z);
                    if(z==f)
                    {
                        cout<<P[z]-1;
                        return;
                    }
                }
            }
        }
        cout<<"-1";
    }
    public:void sol()
    {
        string t="";
        int k;
        for(int i=0;i<9;i++)
        {
            char z;
            cin>>z; t.push_back(z);
            if(z=='0') k=i;
        }
        s={k,t};
        t="";
        for(int i=0;i<9;i++)
        {
            char z;
            cin>>z;t.push_back(z);
            if(z=='0') k=i;
        }
        f={k,t};
        BFS();
    }
};
int main()
{
    tacanh T; T.sol();
}