Knight's journey (Time Limit Exceeded)

[kaushik_acharya]

http://poj.org/problem?id=2488

My solution: DFS with backtracking
But I received Time Limit Exceeded

Here's the pseducode:

Code: Select all

class Position
{
    std::set<T> setJumpPos_; // possible positions to which the Knight can go from the current position.
}

class Board
{
    std::vector<Position<T> > vecPos_;
    bool compute_path_recursive(T pos, std::vector<T>& path);
    void compute_possible_moves();
}

compute_possible_moves()
/*
This is called for all the squares of the board. It populates setJumpPos_ for each of the position.
Its done in initialization stage.
*/

Code: Select all

/*
Here I do the DFS in a recursive manner.
*/
bool compute_path_recursive(T pos, std::vector<T>& path)
{
   	vecExplored_[pos] = true;
	path.push_back(pos);

	if (path.size() == nPos_)
	{
		return true;
	}

	bool path_found_flag = false;
	std::set<T> jumpSet = vecPos_[pos].jumpPos();

        // Trying out each of the next jump position from the current pos in a lexicographic manner.
	for (std::set<T>::iterator it = jumpSet.begin(); it != jumpSet.end(); ++it)
	{
		if (!vecExplored_[(*it)])
		{
			if (compute_path_recursive((*it),path))
			{
				path_found_flag = true;
				break;
			}
		}
	}

	if (!path_found_flag)
	{
		vecExplored_[pos] = false;
		path.pop_back();
	}

	return path_found_flag;
}

Unable to figure out what change I can do to get my solution accepted from TLE.

[brianfry713]

I just got AC using DFS in 16MS. Instead of a set describing knight moves, I used this to check the 8 neighbors of a square:
int dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2};

Instead of passing a path vector to a recursive function, I kept a 26 by 2 int array to store the history.

You could also run your code on the below input, hard code and just print the results, I just got AC in 0MS using that method.

Code: Select all

91
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
4 1
4 2
4 3
4 4
4 5
4 6
5 1
5 2
5 3
5 4
5 5
6 1
6 2
6 3
6 4
7 1
7 2
7 3
8 1
8 2
8 3
9 1
9 2
10 1
10 2
11 1
11 2
12 1
12 2
13 1
13 2
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1

[jony33]

What is the time complexity of Sieve of Eratosthenes algorithm to find prime numbers?