Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

yash1402_'s blog

By yash1402_, history, 4 years ago, In English

I was reading antti lakesonen's competitive programming handbook and I came across backtracking for finding grid paths with some optimizations applied. In nutshell here are the rules for a valid path across the grid :

0. Path search starts from top left cell and ends at bottom right cell.

1. A valid path has traversed all the cells of the grid once.

2. From current cell you can move right, left, top, bottom and only if the move doesn't leave the grid.

Now I have written this code that works fine with square grid of dimension = 7 with time taken ~400ms and total paths : 111712. I have two queries here :

--> With dimension = 9 its taking like a lot of time to report even the first valid path in its search. Am I stuck into the infinite loop or what?

--> Grid path search for even number of dimension like 2,4,6 are giving answer 0. I tried with finding path for 2*2 and 4*4 grid manually but I see that it's impossible to find such paths, but i don't know how to formally or logically prove that even dimensions square grids cannot have such paths mentioned above.

Here is my code

Just comment ARRAY_BASED_CONSTANT_GRID to enable user input for grid dimension.

Can someone help me with this? Thanks in advance :)

  • Vote: I like it
  • 0
  • Vote: I do not like it