runtah: UVa 439 Knight Moves

Saturday, October 1, 2016

UVa 439 Knight Moves

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <queue>
#include <algorithm>

#define INF 9999999
#define MAXX 9
#define MAXW 9
using namespace std;
typedef struct v
{
 int row, col;
} vtx;
vtx moves[10]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};

char inp[1000];

bool color[10][10];
int d[10][10];
int bfs(int srow, int scol, int drow, int dcol)
{
 int i, j;
 for (i=0 ; i<=MAXX ; i++)
 for (j=0 ; j<=MAXW ; j++)
 {
 color[i][j]=false;
 d[i][j]=INF;
 }

 color[srow][scol] = true;
 d[srow][scol] = 0;
 queue<vtx> myq;
 vtx u, t, s;
 s.row=srow;
 s.col=scol;

 myq.push(s);
 while (!myq.empty())
 {
 u = myq.front();
 myq.pop();
 for (i=0 ; i<8; i++)
 {
 t.row = u.row+moves[i].row;
 t.col = u.col+moves[i].col;
 if (t.row>=1 && t.row<MAXX && t.col>=1 && t.col<MAXW && color[t.row][t.col]==false)
 {
 //cout << "-> " << t.row << " " << t.col << endl;
 //getchar();
 color[t.row][t.col]=true;
 d[t.row][t.col]=d[u.row][u.col]+1;
 if (t.row == drow && t.col == dcol) return d[t.row][t.col];
 myq.push(t);
 }
 //cout << "--> " << "lOOPing" << endl;
 }
 //if (myq.empty()) return d[drow][dcol];
 //myq.pop();
 }

 return d[drow][dcol];
}

int main()
{
 int scol, srow, dcol, drow;
 char sc,dc;
 while (gets(inp))
 {
 sscanf(inp,"%c%d %c%d",&sc,&srow,&dc,&drow);
 scol = sc-a+1;
 dcol = dc-a+1;
 srow; drow;

 //printf("%d %d %d %d ",srow,scol,drow,dcol);
 //getchar();

 printf("To get from %c%d to %c%d takes %d knight moves. ",sc,srow,dc,drow,bfs(srow,scol,drow,dcol));
 }
 return 0;
}
Go to link download