OJ Board

Hello all

Plz give ur ideas n suggestions:

We define an n × n grid to be an undirected graph (V,E)
where V = {(i, j) | 1 ? i ? n, 1 ? j ? n}, and two vertices (i, j) and (i?, j?)
are adjacent iff either i = i? and j = j?±1 or j = j? and i = i?±1. Thus, each
vertex in a grid has at most 4 neighbors. We call the vertices with fewer than
4 neighbors boundary vertices (i.e., these are vertices (1, j), (n, j), (i, 1), or
(i, n)). Give an O(m.n^2) algorithm which takes a value n ? N and m ? n^2
starting vertices (i, j) ? [1..n]×[1..n] and determines whether there exists a
set of m vertex-disjoint paths in the n × n grid, each connecting a starting
node with a boundary node.

Thanks n Regards

That's problem 563 (Crimewave) on this online judge. It's also called an 'escape problem' in some exercise in CLRS.

Build the graph with vertex capacities, and use DFS to find augmenting paths - it'll run in O(mn^2) time.

Plz give ur ideas n suggestions:

Please use a spellchecker.

thanks for the reply
i am sorry for the spellings.


Can you please suggest something for this problem:

A path cover of a directed graph is a set of paths such
that every vertex is included in exactly one path. The size of a path cover is
the number of paths in the set. Show how to reduce the problem of finding
a minimum-sized path cover in a directed acyclic graph to the problem of
finding a maximum-sized matching in a bipartite graph. The total running
time of the algorithm should be in O(na).

Thanks and regards