Problem link : H1 Problem - CodeChef
Please help, it’s high time.
Showing TLE for my code :
“”"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl “\n”
#define mod 1000000007
#define MAXN 100005
void swap(int& x, int& y)
{int temp = x; x = y; y = temp;}
vector adj[9];
bool chk(int x)
{
for(int i = 2; i<x; i++)
{
if(x%i==0)
return false;
}
return true;
}
int solve()
{
string s;
int x, y;
for(int i = 0; i<9; i++)
{
cin>>x;
s += ‘0’ + x;
}
adj[0].push_back(1);
adj[0].push_back(3);
adj[1].push_back(2);
adj[1].push_back(4);
adj[2].push_back(5);
adj[3].push_back(4);
adj[3].push_back(6);
adj[4].push_back(5);
adj[4].push_back(7);
adj[5].push_back(8);
adj[6].push_back(7);
adj[7].push_back(8);
string temp = “123456789”;
queue q;
q.push(s);
int ans = 0;
int size;
string t;
set st;
while(!q.empty())
{
ans++;
size = q.size();
for(int j = 0; j<size; j++)
{
auto p = q.front();
q.pop();
if(p==temp)
return ans-1;
for(int i = 0; i<9; i++)
{
t = p;
x = t[i] - '0';
for(auto it : adj[i])
{
y = t[it] - '0';
if(chk(x+y))
{
swap(t[i], t[it]);
if(st.find(t)==st.end())
q.push(t);
}
}
}
}
}
return -1;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int t = 1;
cin>>t;
while(t–)
{
int x = solve();
cout<<x<<endl;
}
return 0;
}
“”"