backtracking
Another backtracking problem. As you can see in the problem description you are not allowed to pass each edge twice. ( Euler tour in lexicographical order )
I make an adjacency matrix, and a boolean matrix for marking the edges I have visited till now.
int mat[6][6];
bool mark[6][6];
Then I start backtracking from node 1 and each time checking whether to continue from current node or not I check ( mark[cur][i] == false && mat[cur][i] == 1 ) and then mark this edge to true and keep on backtracking. I have a variable d which denotes the depth of the backtracking whenever it reaches 9 I completely print the tour I have saved.
I describe my solution or give some hints about the solution for algorithmic problems used in ICPC or online sites for programming contests.
Wednesday, August 26, 2009
Subscribe to:
Post Comments (Atom)
USACO - Prime Palindromes
I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...
-
Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se...
-
Link to the problem on Timus Online Judge The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know...
-
Link to the problem on Timus Online Judge This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...
hey dude, this hint is very good. it's useful for me.
ReplyDeletekeep good work.