10085 - The most distant state

[sidky]

I solved this problem with simple bfs and it took me almost 10 seconds. But i saw that many people have solved that in 0.000 seconds. Can anyone please help me how can i attain such speed?

[junjieliang]

This might be a spoiler, but... skip this part if you don't want to know.








Precalculation
Notice that the answer depends ONLY on when the empty slot is, that is if the empty slot is in the lower left corner (as in sample input), the path is ALWAYS "UURDDRULLURRDLLDRRULULDDRUULDDR". So you will only have 9 different states to precalculate, after which you do some simply array manipulation.

[CC]

consider the symmetry effect
so there are only three status ( corner, mid-boundary and central)
input and output give two, the last is to be precalculated

[lonelyone]

Hi all:
I know there are many algorithm can be used to solve this problem quickly.
But somehow I wanna use DFS to solve this problem.

Problem Description:
Given a board state, I wanna use DFS to find the shortest path from Init state to Goal state(123456780).

Obviously, use DFS it should visit all possible branches(9!).
But the speed is not the serious problem, the most serious problem is the memory usage of DFS. It should memorize some information to maintain a stack. For example, zero position, path, board state, etc. So if I use recurtion and the stack is maintained by Computer. My program would crash because of stack overflow.

And then I use customize stack to simulate it. However, I encounter a problem that there are many same substates, some of them are at different depth. Then how should I do?

Below is my code, but it is wrong.
Anyone would help me out, or help me to revise it, or give me your code of DFS version. I will appreciate you alot.

Code: Select all

..cut

You may use the test case below.
Obviously, there is one shortest solution, it is RDD.

Code: Select all

1
1 0 2
4 5 3
7 8 6

Lonely

[mf]

Given a board state, I wanna use DFS to find the shortest path from Init state to Goal state

DFS can't help you here. When you want shortest path, use BFS.

And then I use customize stack to simulate it. However, I encounter a problem that there are many same substates, some of them are at different depth.

That's exactly why you got all those stack overflows and excessive memory usage.
If you don't skip previously-visited states, DFS visits something like O(4^depth) states, and in the worst case shortest solution needs 31 moves.

Use some date structure to remember which states were already visited, and when there's a move from current state to one of those, just ignore it.

[lonelyone]

First of all, thanks for your kindness and response.

I wanna know why in the worst case shortest solution only needs 31 moves.

Can you explain it in some details.

Lonely

[mf]

I wanna know why in the worst case shortest solution only needs 31 moves.

I've solved problem 10085 (with BFS), and my program says so.

[datahaven]

The discussion above is very dependent on how you interpret the problem statement.

There is nowhere in the problem statement that says that the integers on the tiles have to be either in the range 1-8 or, more importantly, unique numbers.

1 1 1
1 1 1
0 1 1

has a most distant state of

1 1 0
1 1 1
1 1 1
UURR
(or many other similar possible move combinations)

which your precalculated solution would fail on if you consider all states with a space in the same position to be the same.

Of course the large number of very quick pre-calculated solutions might suggest that the judge isn't testing this case and that it is actually the problem that is badly worded.

Adrian

[just_yousef]

my code with map<string,int> was too slow so i tried to use hashing but i always get a path mush longer than the answer
this is my code

Code: Select all

#include<bits/stdc++.h>
using namespace std;

int t, dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 }, state[10], par[1000000],
		vist[1000000], id;
char move[5] = "URDL";

struct node {
	int state[10], pos, dir;
} arr[1000003];
int hash(int *a) {
	int ans = 0;
	for (int i = 0; i < 9; ++i)
		ans = ans * 10 + a[i];
	return ans % 1000003;
}
void print_path(int x) {
	if (x == -1)
		return;
	print_path(par[x]);
	putchar(move[arr[x].dir]);
}
int main(int argc, char **argv) {
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
#endif
	for (scanf("%d", &t); t--;) {
		int pos = -1;
		for (int i = 0; i < 9; ++i) {
			scanf("%d", &state[i]);
			if (state[i] == 0)
				state[i] = 9, pos = i;
		}
		int hs = hash(state), x;
		vist[hs] = ++id;
		arr[hs].pos = pos;
		memcpy(arr[hs].state, state, sizeof state);
		memset(par, -1, sizeof par);
		queue<int> que;
		que.push(hs);
		while (que.size()) {
			x = que.front();
			que.pop();
			for (int i = 0; i < 4; ++i) {
				int a = arr[x].pos / 3 + dx[i], b = arr[x].pos % 3 + dy[i];
				if (a < 0 || b < 0 || a > 2 || b > 2)
					continue;
				memcpy(state, arr[x].state, sizeof arr[x].state);
				swap(state[arr[x].pos], state[a * 3 + b]);
				hs = hash(state);
				if (vist[hs] == id)
					continue;
				vist[hs] = id;
				que.push(hs);
				arr[hs].pos = a * 3 + b;
				memcpy(arr[hs].state, state, sizeof state);
				par[hs] = x;
				arr[hs].dir = i;
			}
		}
		static int cas = 1;
		printf("Puzzle #%d\n", cas++);
		for (int i = 0; i < 9; ++i) {
			if (arr[x].state[i] == 9)
				arr[x].state[i] = 0;
			printf("%d%c", arr[x].state[i], (i + 1) % 3 == 0 ? '\n' : ' ');
		}
		print_path(x);
		puts("");
	}
	return 0;
}

[brianfry713]

After each test case output an empty line.

[just_yousef]

no my problem in the first place that it produces answers with longer path.
and i don't know why ??