← Home
For problem statement at 0-999/700-799/770-779/778/problemD.txt this is a correct solution, but verifier at 0-999/700-799/770-779/778/verifierD.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n, m int
	if _, err := fmt.Fscan(reader, &n, &m); err != nil {
		return
	}

	startGrid := make([][]byte, n)
	for i := 0; i < n; i++ {
		var s string
		fmt.Fscan(reader, &s)
		startGrid[i] = []byte(s)
	}

	targetGrid := make([][]byte, n)
	for i := 0; i < n; i++ {
		var s string
		fmt.Fscan(reader, &s)
		targetGrid[i] = []byte(s)
	}

	H_start := getH(startGrid, n, m)
	H_target := getH(targetGrid, n, m)

	var ops [][2]int

	for sweeps := 0; sweeps < 100000; sweeps++ {
		foundDiff := false
		flipped := false

		for x := 1; x < n; x++ {
			for y := 1; y < m; y++ {
				if H_start[x][y] == H_target[x][y] {
					continue
				}
				foundDiff = true

				isHoriz := startGrid[x-1][y-1] == 'L' && startGrid[x-1][y] == 'R' &&
					startGrid[x][y-1] == 'L' && startGrid[x][y] == 'R'
				isVert := startGrid[x-1][y-1] == 'U' && startGrid[x][y-1] == 'D' &&
					startGrid[x-1][y] == 'U' && startGrid[x][y] == 'D'

				cVal := 1
				if (x-1+y-1)%2 != 0 {
					cVal = -1
				}

				if isHoriz {
					delta := 4 * cVal
					if (H_start[x][y] < H_target[x][y] && delta > 0) || (H_start[x][y] > H_target[x][y] && delta < 0) {
						startGrid[x-1][y-1] = 'U'
						startGrid[x][y-1] = 'D'
						startGrid[x-1][y] = 'U'
						startGrid[x][y] = 'D'
						H_start[x][y] += delta
						ops = append(ops, [2]int{x, y})
						flipped = true
					}
				} else if isVert {
					delta := -4 * cVal
					if (H_start[x][y] < H_target[x][y] && delta > 0) || (H_start[x][y] > H_target[x][y] && delta < 0) {
						startGrid[x-1][y-1] = 'L'
						startGrid[x-1][y] = 'R'
						startGrid[x][y-1] = 'L'
						startGrid[x][y] = 'R'
						H_start[x][y] += delta
						ops = append(ops, [2]int{x, y})
						flipped = true
					}
				}
			}
		}

		if !foundDiff {
			break
		}
		if !flipped {
			fmt.Println("-1")
			return
		}
	}

	if len(ops) > 100000 {
		fmt.Println("-1")
		return
	}

	fmt.Println(len(ops))
	writer := bufio.NewWriter(os.Stdout)
	for _, op := range ops {
		fmt.Fprintln(writer, op[0], op[1])
	}
	writer.Flush()
}

func getH(grid [][]byte, n, m int) [][]int {
	H := make([][]int, n+1)
	for i := range H {
		H[i] = make([]int, m+1)
	}
	H[0][0] = 0
	for x := 0; x <= n; x++ {
		for y := 0; y <= m; y++ {
			if x == 0 && y == 0 {
				continue
			}
			if y > 0 {
				weight := 1
				if x > 0 && x < n && grid[x-1][y-1] == 'U' && grid[x][y-1] == 'D' {
					weight = -3
				}
				cVal := 1
				if (x+y-1)%2 != 0 {
					cVal = -1
				}
				H[x][y] = H[x][y-1] + cVal*weight
			} else if x > 0 {
				weight := 1
				cVal := 1
				if x%2 != 0 {
					cVal = -1
				}
				H[x][0] = H[x-1][0] + cVal*weight
			}
		}
	}
	return H
}