Knight's journey (Time Limit Exceeded)

Moderator: Board moderators

kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

Knight's journey (Time Limit Exceeded)

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.
My experience with Fraudster khari

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Knight's journey (Time Limit Exceeded)

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
``````
Check input and AC output for thousands of problems on uDebug!

jony33
New poster
Posts: 2
Joined: Sat Oct 11, 2014 11:56 am

Re: Knight's journey (Time Limit Exceeded)

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