The zip file should contain your source code along with a report (PDF) containing the algorithm in pseudo-code format. Your source code can be any of the following: C, C++, Java, Python and/or Matlab.. For evaluation, we will be testing with our own set of inputs.
PROBLEM: An n × n grid is an undirected graph consisting of n rows and n columns of vertices, as shown in the figure below. We denote the vertex in the ith row and the jth column by (i,j). All vertices in a grid have exactly four neighbors, except for the boundary vertices, which are the points (i,j) for which i = 1,i = n,j = 1, or j = n. Given m ≤ n2 starting points (x1,y1), (x2,y2), . . . (xm,ym) in the grid, the Funny Problem is to determine whether or not there are m vertex-disjoint paths from the starting points to any m different (distinct) points on the boundary. Two paths P1 and P2 are said to be vertex disjoint if they don’t have any common vertex present in both the paths. For example,the the Funny Problem has a solution in the grid shown in Figure (a) (the vertex disjoints paths are shown by grey lines), whereas the grid shown in Figure (b) does not.
This programming assignment will take as input: (i) an integer number n (for creating the n × n grid), and (ii) m grid points (m ≤ n2, specified by their row-column values i × j). The output of the assignment will be (i) A Yes/No answer to whether a solution to the Funny Problem exists for the input problem instance, and (ii) If the answer to (i) is Yes, the vertex-disjoint paths that constitute the solution.
Figure 1: Grids for the escape problem. Starting points are black, and other grid vertices are white.
