Informatica Interview Question
iOS DevelopersTeam: interviews
Country: United States
Interview Type: Written Test
#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 3
/*
coordinates of the map
> X





Y
*/
struct Point{ //coordinate of a point
int y, x;
};
int N; //map's row and col size
char map[MAX][MAX+1]; //map's state
int prePos[MAX*MAX]; //prePos[i] is the previous position of i, i/N is row, i%N is col
const int step[][2] = { //8 kinds of steps of knight > (dy, dx)
{2,1},{1,2},{1,2},{2,1},
{2,1},{1,2},{1,2},{2,1}
};
void markPath(int y, int x)
{
int now, pre;
for(now = y*N + x; (pre = prePos[now]) >= 0; now = pre){
map[pre/N][pre%N] = '@';
}
}
bool bfs()
{
int i;
//step 1: find start and destination
int sy, sx, dy, dx;
char* p;
for(i = 0; i < N; ++i){ //find start
if(p = strchr(map[i], '@')){
sy = i;
sx = p  map[i];
break;
}
}
if(p[1] && (p = strchr(p+1, '@'))){//if destination is at the same row
dy = i;
dx = p  map[i];
}
else{ //destination is at different row
for(++i; i < N; ++i){
if(p = strchr(map[i], '@')){
dy = i;
dx = p  map[i];
break;
}
}
}
//step 2: bfs to find the shortest path from start to destination
memset(prePos, 0xFF, sizeof(prePos));
Point now, nex;
int nowIndex, nexIndex;
queue<Point> q;
now.y = sy;
now.x = sx;
q.push(now);
while(!q.empty()){
now = q.front();
if(now.y == dy && now.x == dx){ //find path!
markPath(dy, dx); //mark path in the map
return true;
}
//get represent index of point now
nowIndex = now.y*N + now.x;
for(i = 0; i < 8; ++i){
nex.y = now.y + step[i][0];
nex.x = now.x + step[i][1];
if(nex.y < 0  nex.y >= N  //y out of border
nex.x < 0  nex.x >= N  //x out of border
map[nex.y][nex.x] == '#') continue;//it's a cut cell
//get represent index of point nex
nexIndex = nex.y*N + nex.x;
if(prePos[nexIndex] >= 0) continue; //already visited
//add nex point to position queue
prePos[nexIndex] = nowIndex;
q.push(nex);
}
}
return false;
}
int main()
{
int i;
//input map size
scanf("%d", &N);
while(getchar() != '\n');
//input each row
for(i = 0; i < N; ++i) gets(map[i]);
//bfs search path
if(bfs()){//can go
for(i = 0; i < N; ++i) puts(map[i]);
}
else puts("Impossible");
return 0;
}
#include <iostream>
#include <ctime>
using namespace std;
const int N = 8;
int map[N][N];
/* A utility function to check if i,j are valid indexes for N*N chessboard */
bool isSafe(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && map[x][y] == 1;
}
/* A utility function to print solution matrix sol[N][N] */
void printSolution() {
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
cout << map[x][y];
cout << endl;
}
}
/* A recursive utility function to solve Knight Tour problem */
bool knightsTourRecursive(int x, int y, int movei, int xMove[N], int yMove[N]) {
int nextX, nextY;
if (movei == N*N)
return true;
/* Try all next moves from the current coordinate x, y */
for (int k = 0; k < 8; k++) {
nextX = x + xMove[k];
nextY = y + yMove[k];
if (isSafe(nextX, nextY)) {
map[nextX][nextY] = movei;
if (knightsTourRecursive(nextX, nextY, movei+1, xMove, yMove)) // recursion
return true;
else
map[nextX][nextY] = 1; // backtracking
}
}
return false;
}
bool knightsTour() {
/* Initialization of solution matrix */
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
map[x][y] = 1;
/* xMove[] and yMove[] define next move of Knight.
xMove[] is for next value of x coordinate
yMove[] is for next value of y coordinate */
int xMove[8] = { 2, 1, 1, 2, 2, 1, 1, 2 };
int yMove[8] = { 1, 2, 2, 1, 1, 2, 2, 1 };
int initX = rand() % N;
int initY = rand() % N;
cout << "Starting at " << initX << " " << initY << endl;
// Since the Knight is initially at the first block
map[initX][initY] = 0;
/* explore all tours using solveKTUtil() */
if(!knightsTourRecursive(initX, initY, 1, xMove, yMove) ) {
cout << "Solution does not exist" << endl;
return false;
}
else
printSolution();
return true;
}
int main() {
srand( (unsigned) time(0));
knightsTour();
cin.get();
return 0;
}
Well, you could reformulate the problem as shortest path on a graph with edge weights 1, where each square on the board is a node, and its neighbours are all the nodes the knight can go to from there. If a part is cut, then obviously the node doesn't exist. The shortest path is simply given by BFS (since all edge weights are the same), so it should take O(nodes + edges ) time which is O(n^2 + 8(n^2)) which is O(n^2)
 Gaumrox December 25, 2013