ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1035. Cross-stitch

How to create a graph in this problem
Posted by Karolis Kusas 1 Jul 2011 18:00
Hello,

I tried to create a graph for this problem in this way:
Vertices correspond to intersections of the board (left upper (0; 0) and right lower (n; m)).
I will denote the vertice by [i][j][l]. If i = 0, then we have face of the cloath, else if i = 1, we have the rear of the cloth. j means the row, and l - column.

For the example test, graph edges:
[0][1][1] <-> [1][2][2]
[0][2][2] <-> [1][1][1]
[0][2][2] <-> [1][3][3]
[0][3][3] <-> [1][2][2]
[1][2][1] <-> [0][3][2]
[1][2][2] <-> [0][3][3]
[1][2][3] <-> [0][3][2]
[1][2][5] <-> [0][1][4]
[1][3][2] <-> [0][2][1]
[1][3][2] <-> [0][2][3]
[1][3][3] <-> [0][2][2]

I can not count degrees correctly with this graph even for the example test. Is there a better graph representation? If no, how to solve the problem with this one?