2019-1A Problem A

Final solution

// package, import, etc...

func start() {
	var t int
	mustReadLineOfInts(&t)
	for i := 0; i < t; i++ {
		fmt.Fprintf(stdout, "Case #%d: ", i+1)
		var R, C int
		mustReadLineOfInts(&R, &C)
		test(R, C)
	}
}

type Point struct {
	r, c int
}

func printGrid(grid [][]bool) {
	return
	// stderr := os.Stderr
	// stderr.WriteString("\033[s\n")
	// for r := 0; r < len(grid); r++ {
	// 	for c := 0; c < len(grid[r]); c++ {
	// 		if grid[r][c] {
	// 			stderr.Write([]byte{'*'})
	// 		} else {
	// 			stderr.Write([]byte{' '})
	// 		}
	// 	}
	// 	stderr.Write([]byte{'\n'})
	// }
	// stderr.WriteString("\033[u")
	// time.Sleep(50 * time.Millisecond)
}

func findPath(grid [][]bool, trail []Point, trailLen int) bool {
	printGrid(grid)
	R := len(grid)
	C := len(grid[0])
	if trailLen == R*C {
		return true
	}
	candidatePoints := make([]Point, 0)
	for r := 0; r < R; r++ {
		for c := 0; c < C; c++ {
			if grid[r][c] {
				continue
			}
			if trailLen == 0 {
				candidatePoints = append(candidatePoints, Point{r, c})
			} else {
				lastPoint := trail[trailLen-1]
				assert(grid[lastPoint.r][lastPoint.c])
				if lastPoint.r == r {
					break // skip this row
				}
				if lastPoint.c == c {
					continue
				}
				if lastPoint.r-lastPoint.c == r-c || lastPoint.r+lastPoint.c == r+c {
					continue
				}
				candidatePoints = append(candidatePoints, Point{r, c})
			}
		}
	}
	if len(candidatePoints) == 0 {
		return false
	} else {
		shufflePoints(candidatePoints)
		for _, cp := range candidatePoints {
			grid[cp.r][cp.c] = true
			trail[trailLen] = Point{cp.r, cp.c}
			ok := findPath(grid, trail, trailLen+1)
			if !ok {
				grid[cp.r][cp.c] = false
				continue
			}
			return true
		}
		return false
	}
}

// CJ's runner runs go 1.7.4

func shufflePoints(ps []Point) {
	for i := 0; i < len(ps)-1; i++ {
		j := rand.Intn(len(ps)-i) + i
		ps[i], ps[j] = ps[j], ps[i]
	}
}

func test(R, C int) {
	if R <= 2 && C <= 2 {
		output(false)
		return
	}
	grid := make([][]bool, R)
	for r := 0; r < R; r++ {
		grid[r] = make([]bool, C)
	}
	trail := make([]Point, R*C)
	ok := findPath(grid, trail, 0)
	printGrid(grid)
	output(ok)
	if ok {
		for _, r := range trail {
			fmt.Fprintf(stdout, "%d %d\n", r.r+1, r.c+1)
		}
	}
}

func output(possible bool) {
	if possible {
		stdout.WriteString("POSSIBLE\n")
	} else {
		stdout.WriteString("IMPOSSIBLE\n")
	}
}

// boilerplate omitted...

Sample test cases given in question

3
2 2
2 5
20 20