UVA – 10422 – Knights in FEN

  • Problem Statement : UVA – 10422 – Knights in FEN
  • Type : DFS, BFS
  • Solution :
    • I used BFS for this solution although most codes I’ve seen was DFS ^o)
    • I used the STL  tree map but I believe the map could be serialized and hashed that may give a better time. I think taht what made the time difference but I don’t think it beat the visited flagging ^o)
    • There is an Optimization that will boost the time for both implementations, It was to notice that if currently in this branch the remaining no of differences to reach the desired state is larger than the no of moves left to reach 11 moves. so it doesn’t worth to continue in this branch, so drop it and continue.
  • Other Solutions :
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<string.h>
#include<map>
#include <queue>
using namespace std;
#define FOR(ii, i0, in) for((ii)=(i0); (ii)<(in); ++(ii))
#define FOR2d(ii, jj, i0, j0, in, jn) FOR(ii, i0, in) FOR(jj, j0, jn)
#define FOR3d(kk, ii, jj, k0, i0, j0, kn, in, jn) FOR(kk, k0, kn) FOR(ii, i0, in) FOR(jj, j0, jn)
char final[5][6] = { "11111", "01111", "00 11", "00001", "00000" };
int dx[] = { -2, -2, 2, 2, -1, 1, -1, 1, 0 }, dy[] = { -1, 1, -1, 1, -2, -2, 2,
		2, 0 };
char r[5][6], start[5][6];

struct Point {
	int i, j;
	Point() {}
	Point(int y, int x) { i = y, j = x; }
	Point moveTo(int d) { return Point(i + dy[d], j + dx[d]); }
	bool valid() 		{ return i >= 0 && j >= 0 && i < 5 && j < 5; }
};
struct State {
	char b[5][6];
	Point origin;
	int d;
	State(char B[5][6], Point p, int D) {
		memcpy(b, B, sizeof b);
		this->origin = p;
		this->d = D;
	}
	State moveFrom(Point p) {
		State to(this->b, p, d + 1);
		swap(to.b[p.i][p.j], to.b[origin.i][origin.j]);
		return to;
	}
};
bool operator<(State s1, State s2) {
	return memcmp(s1.b, s2.b, 30 * sizeof(char)) < 0;
}

int MASK(char state[5][6])
{
    int d(0), a, b;
    FOR2d(a, b, 0, 0, 5, 5)
    	d+=(state[a][b]!=final[a][b]);
    return (d/2);
}

int main() {
	int i, j, T;
	string line;
	Point origin;
	scanf("%d", &T);
	getchar();
	while (T--) {
		FOR2d(i, j, 0, 0, 5, 5){
			scanf("%c", &start[i][j]);
			if (start[i][j] == ' ') origin = Point(i, j);
			if (j == 4) r[i][5] = getchar() - '\n';
		}
		map<State, bool> visited;
		queue<State> que;
		que.push(State(start, origin, 0));
		while (que.size()) {
			State u = que.front();
			if (u.d >= 11 || memcmp(final, u.b, 30 * sizeof(char)) == 0) break;
			que.pop();
			if(u.d+ MASK(u.b) >=11) continue;
			for (int i = 0; i < 8; ++i) {
				Point newO = u.origin.moveTo(i);
				if (newO.valid() && !visited[u.moveFrom(newO)]) {
					State v = u.moveFrom(newO);
					que.push(v);
					visited[v] = true;
				}
			}
		}
		if (memcmp(final, start, 30 * sizeof(char)) == 0)
			printf("Solvable in %d move(s).\n", 0);
		else if (que.empty() || que.front().d >= 11 || !visited[que.front()])
			printf("Unsolvable in less than 11 move(s).\n");
		else
			printf("Solvable in %d move(s).\n", que.front().d);

	}
	return 0;
}

Advertisements

One thought on “UVA – 10422 – Knights in FEN

  1. Shafiul Azam says:

    It works. You can check input/output compiling the code online here: http://bit.ly/taaTMq

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: