GridSort | Topcoder Archive

Problem Statement

Charlie has a grid of n rows by m columns. The rows are numbered 0 through n-1 from top to bottom. The columns are numbered 0 through m-1 from left to right.

Each cell of the grid contains a positive integer. The integers in Charlie's grid are a permutation of the numbers 1 through n*m. (I.e., each of these numbers occurs in the grid exactly once.)

Given a grid, its value list is a sequence constructed by listing all values in the grid in row major order. That is, we first list the values in row 0 from left to right, then the values in row 1 from left to right, and so on.

You are given the ints n and m: the dimensions of Charlie's grid. You are also given a int[] grid: the value list for Charlie's grid. (Formally, grid[i*m+j] is the value stored in row i, column j of the grid.)

Charlie can modify his grid in two ways: He may swap any two rows, and he may swap any two columns. Charlie now wonders whether there is a sequence of swaps that would sort his grid - that is, rearrange its elements in such a way that the value list of the new grid will be the ordered sequence (1,2,3,...,n*m).

If it is possible to sort Charlie's grid, return "Possible". Otherwise, return "Impossible".

Definition

Class:: GridSort
Method:: sort
Parameters:: int, int, int[]
Returns:: String
Method signature:: String sort(int n, int m, int[] grid)
(be sure your method is public)

Constraints

n,m will be between 1 and 50, inclusive.
grid will be a permutation of [1,...,n*m].

Examples

```
2
```
```
2
```
```
{
 1,2,
 3,4
}
```
```
Returns: "Possible"
```
This grid is already sorted, so Charlie doesn't need to do anything.
```
2
```
```
2
```
```
{
 3,4,
 1,2
}
```
```
Returns: "Possible"
```
Charlie can sort this grid by swapping rows 0 and 1.
```
2
```
```
2
```
```
{
 4,3,
 1,2
}
```
```
Returns: "Impossible"
```

{4,5,1,2,9,8,3,10,7,6}

Returns: "Possible"

{
 10,6,8,9,7,
 5,1,3,4,2,
 15,11,13,14,12
}

Returns: "Possible"

{
 11,12,
 2,1,
 9,10,
 7,8,
 6,5,
 3,4
}

Returns: "Impossible"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.