I'm trying to solve this problem using BFS codeforces.com/problemset/problem/3/A.
I could find the shortest path using BFS, but I'm unable to trace the path. How am I supposed to do that?
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
bool g[9][9];
class node{
public:
int x;
int y;
node(int X, int Y)
{
x=X;
y=Y;
}
};
int main()
{
map<char, int> mymap;
char sc; int sn; char dc; int dn;
scanf("%c%d", &sc, &sn); cin.ignore();
scanf("%c%d", &dc, &dn);
//cout<<sc<<" "<<sn<<" "<<dc<<" "<<dn<<endl;
for(int i=0; i < 8; i++)
{
char current=char(i+97);
mymap[current]=i+1;
}
map<char, int>::iterator it;
//for(it = mymap.begin(); it!= mymap.end(); it++)
// cout<<it->first<<" :-> "<<it->second<<endl;
int a,b;
a=mymap.find(sc)->second;
b=mymap.find(dc)->second;
//cout<<x<<" "<<y<<endl;
//int dx[]={1, 0, -1, 1}
//int dy[]={1, -1, 0, 1}
for(int i = 1 ; i <= 8; i++)
for(int j=1; j <= 8; j++)
g[i][j]=false;
//int distance[8];
//memset(distance, 8, 0);
int distance=0;
queue<node> Q;
Q.push(node(a,sn));
int r=1, c=1;
while(!Q.empty())
{
node current=Q.front();
Q.pop();
if(current.x < 1 || current.x > 8 ) continue;
if(current.y <1 || current.y > 8) continue;
if(g[current.x][current.y]) continue;
g[current.x][current.y]=true;
if(current.x>r && current.y > c)
{
r=current.x;
c=current.y;
distance++;
}
if(current.x==b && current.y == dn)
break;
Q.push(node(current.x + 1, current.y));
Q.push(node(current.x - 1, current.y));
Q.push(node(current.x, current.y + 1));
Q.push(node(current.x, current.y - 1));
Q.push(node(current.x-1, current.y-1));
Q.push(node(current.x+1, current.y-1));
Q.push(node(current.x+1, current.y+1));
Q.push(node(current.x+1, current.y-1));
}
cout<<distance<<endl;
return 0;
}
