UVA 10422 / Backtrack

/***
 created: 2022-07-15-19.20.12
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define get_lost_idiot return 0
#define nl '\n'


ll dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
ll dy[8] = {-1, 1, -2, 2, 2, -2, 1, -1};
char cc[5][6]= {"11111","01111","00 11","00001","00000"};
char a[15][15];
ll cnt=0,exist=0;

void dfs(ll i,ll j,ll ans)
{
    if(ans==cnt)
    {
        ll ee=0;

        for(ll i1=0; i1<5 && !ee; i1++)
        {
            for(ll j1=0; j1<5 && !ee; j1++)
            {
                if(a[i1][j1]!=cc[i1][j1])
                {
                    ee=1;
                    break;
                }
            }
        }

        if(ee==0) exist=1;

        if(exist) return ;
        return;

    }

    if(exist) return ;

    for(ll ii=0; ii<8; ii++)
    {

        ll xx=i+dx[ii];
        ll yy=j+dy[ii];

        if(xx>=0 && xx<5 && yy>=0 && yy<5)
        {
            swap(a[i][j],a[xx][yy]);
            dfs(xx,yy,ans+1);
            swap(a[i][j],a[xx][yy]);
        }
    }
}



int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt;

    cin>>tt;

    cin.ignore();

    for(int cs=1; cs<=tt; cs++)
    {
        int i,j,k,l,x,y;

        vector<string>in;
        string b;

        for(i=0;i<5;i++)
        {
            getline(cin,b);
            in.push_back(b);
        }

        for(i=0; i<5; i++)
        {
            for(j=0; j<5; j++)
            {
                a[i][j]=in[i][j];

                if(in[i][j]==' ')
                {
                    x=i,y=j;
                }
            }
        }

        exist=0;

        for(i=0; i<11; i++)
        {
            cnt=i;
            dfs(x,y,0);
            if(exist) break;
        }

        if (exist==0) cout<<"Unsolvable in less than 11 move(s)."<<nl;
        else cout<<"Solvable in "<<cnt<<" move(s)."<<nl;

    }



    get_lost_idiot;
}