Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int mx = 1e6;
- map<string, int> state_to_int; //mapping every state to unique value
- map<int, string> int_to_state; //getting the state for every int value
- string d; // destination state
- int ind = 0; // a variable for representing every state to int
- vector<int> adj[mx + 1];
- vector<int> par(mx + 1, -1);
- int dx[4] = {1, -1, 0, 0};
- int dy[4] = {0, 0, 1, -1};
- int vis[mx + 1];
- void bfs(int strt) {
- queue<int> q;
- q.push(strt);
- while(!q.empty()) {
- int fr = q.front();
- string str = int_to_state[fr];
- q.pop();
- vis[fr] = 1;
- if (str == d) {
- return;
- }
- int x, y, sx, sy;
- for (int i = 0; i < 9; i++) {
- if (str[i] == '0') {
- x = i / 3;
- y = i % 3;
- break;
- }
- }
- for (int i = 0; i < 4; i++) {
- sx = x + dx[i];
- sy = y + dy[i];
- if (sx >= 0 and sx < 3 and sy >= 0 and sy < 3) {
- string tem = str;
- swap(tem[x * 3 + y], tem[sx * 3 + sy]);
- if (state_to_int.find(tem) == state_to_int.end()) {
- state_to_int[tem] = ind;
- int_to_state[ind] = tem;
- ind++;
- adj[fr].push_back(state_to_int[tem]);
- par[state_to_int[tem]] = fr;
- }
- }
- }
- for (int i = 0; i < adj[fr].size(); i++) {
- if (!vis[adj[fr][i]]) {
- q.push(adj[fr][i]);
- vis[adj[fr][i]] = 1;
- }
- }
- }
- }
- int32_t main() {
- // define destination state & map the state to int
- d = "123456780";
- // taking input the source state
- string s = "";
- char c;
- for (int i = 0; i < 3; i++) {
- for (int j = 0; j < 3; j++) {
- cin >> c;
- s += c;
- }
- }
- state_to_int[s] = ind;
- int_to_state[ind] = s;
- ind++;
- memset(vis, 0, sizeof(vis));
- bfs(state_to_int[s]);
- stack<int> st;
- int node = state_to_int[d];
- while(node != -1) {
- st.push(node);
- node = par[node];
- }
- string str;
- while(!st.empty()) {
- str = int_to_state[st.top()];
- st.pop();
- cout << endl;
- for (int i = 0; i < 9; i++) {
- cout << str[i] << " \n"[i % 3 == 2];
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement