CODEWITHSUNDEEP
c++algorithmgraphcycle
user1724072
user1724072

Reputation: 331

How to detect a cycle in a grid in least time complexity possible?

I have a maxiumum 35 character grid it maybe (1x35..5x7) or anything else .The value of each cell on the grid can be binary only.In simulating a game having certain moves which implies a possible change in the grade state after a move .If I have to detect the cycle/the period of this game,what algorithm/data structure can I use in the least possible time complexity? I tried a log n tree based approach to store the state of the grid but it wasn't fast enough for my purpose when the period is larger than 2^17. Is there a technique to perform hashing on the grid state without taking too much memory?

Upvotes: 0

Views: 193

Answers (1)

jspcal
jspcal

Reputation: 51904

the grid is a 35-bit number, so you can store the grid as an integer (on a 64-bit machine) or 2 words on a lesser one. you can keep states you've already seen in a giant direct-address array or a hash table.

Upvotes: 1

Related Questions