Codeforces Round #290 (Div. 2) B. Fox And Two Dots

this one’s a graph problem, one can try hard and write routines for DFS/BFS but this can be easily done using UnionFind (which i realised after 30min),

Pseudo Code:


for i in xrange(len(rows)):
    for j in xrange(len(columns)):
        if graph[i][j] == graph[i][j + 1]:
            if (i, j), (i, j + 1) are already connected:
                print 'Yes'; exit
            connect((i, j), (i, j + 1))
        if graph[i][j] == graph[i + 1][j]:
            if (i, j), (i + 1, j) are already connected:
                print 'Yes'; exit
            connect((i, j), (i + 1, j))
print 'No'

PS: there’s also another cool way mentioned in the editorial, we can find the connected groups and see if no of edges == no of nodes - 1

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s