UVA – 439 SOLUTION

PROBLEM LINK:

UVA-439 KNIGHT MOVES

BFS RELATED PROBLEM

SOLUTION:

//PROGRAMMERS ARE REQUESTED NOT TO COPY AND PASTE THE CODE SOMEWHERE, //THERE BY YOUR EFFICIENCY WILL DECREASE. PLEASE TRY TO UNDERSTAND THE CODE //AND IF YOU FEEL ANY DIFFICULTY PLEASE COMMENT BELOW, WE WILL TRY TO HELP //FURTHER

#include <bits/stdc++.h>
#define FOO pair<int,int>
#define clear(a) memset(a,0,sizeof(a))

using namespace std;
int DX[]={1, -1, 1, -1, 2, 2, -2, -2};
int DY[]={2, 2, -2, -2, 1, -1, 1, -1};
bool visited[10][10];
int level[10][10];
string str1,str2;
void bfs(int a,int b,int c,int d)
{
queue<FOO> q;
clear(visited);
q.push(FOO(a,b));
level[a][b] = 0;
visited[a][b] = true;
while(!q.empty())
{
FOO top = q.front();
q.pop();
if(top.first == c && top.second == d)
{
cout<<“To get from “<<str1<<” to “<<str2<<” takes “<<level[top.first]                                      [top.second]<<” knight moves.”<<endl;
return;
}
for(int i = 0;i<8;i++)
{
int m = top.first + DX[i];
int n = top.second + DY[i];
if((m>=1&&m<=8)&&(n>=1&&n<=8)&&!visited[m][n])
{
visited[m][n] = true;
level[m][n] = level[top.first][top.second] + 1;
q.push(FOO(m,n));
}}
}}
int main()
{

while(cin>>str1>>str2)
{
int x1,y1,x2,y2;
x1 = str1[0] – 96;
y1 = str1[1] – 48;
x2 = str2[0] – 96;
y2 = str2[1] – 48;
bfs(x1,y1,x2,y2);
}
}