GCJ/2017/Qualification/D/main.go

package main

import "fmt"

// MAXN ...
const MAXN int = 100

// N ...
var N int
var row, col []bool
var diag1, diag2 []bool

// < 0 means orignal solution, > 0 means new solution
var crossSol, plusSol [][]int = make([][]int, MAXN), make([][]int, MAXN)

func placeCrosses() {
	for i := 0; i < N; i++ {
		if row[i] {
			continue
		}
		for j := 0; j < N; j++ {
			if col[j] {
				continue
			}
			crossSol[i][j] = 1
			col[j] = true
			break // Important
		}
	}
}

func placePluses() (points int) { // It's important to figure out the state while placing pluses.
	ds := make([]int, 0)
	for i := 0; i < N-1; i++ {
		ds = append(ds, i) // Start alternately from both ends
		ds = append(ds, 2*N-i-2)
	}
	ds = append(ds, N-1)

	for _, d := range ds {
		if diag1[d] {
			points++
			continue
		}
		var i, j int
		if d < N {
			i, j = d, 0
		} else {
			i, j = N-1, d-N+1
		}

		for ; 0 <= i && j < N; i, j = i-1, j+1 {
			if diag2[i-j+N-1] {
				continue
			}

			plusSol[i][j] = 1
			diag2[i-j+N-1] = true
			points++
			break
		}
	}
	return
}

func main() {
	var T int
	fmt.Scan(&T)
	for tc := 1; tc <= T; tc++ {
		var M int
		fmt.Scan(&N, &M)

		row = make([]bool, MAXN) // Init all state
		col = make([]bool, MAXN)
		diag1 = make([]bool, 2*MAXN-1)
		diag2 = make([]bool, 2*MAXN-1)
		for i := 0; i < MAXN; i++ {
			crossSol[i] = make([]int, MAXN)
			plusSol[i] = make([]int, MAXN)
		}

		for i := 0; i < M; i++ {
			var ch string
			var r, c int
			fmt.Scan(&ch, &r, &c)
			r, c = r-1, c-1
			if ch != "+" { // Is not bishop
				crossSol[r][c] = -1
				row[r], col[c] = true, true
			}
			if ch != "x" { // Is not rook
				plusSol[r][c] = -1
				diag1[r+c], diag2[r-c+N-1] = true, true
			}
		}

		placeCrosses()
		plusPoints := placePluses()

		pieces := 0
		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				if 0 < crossSol[i][j] || 0 < plusSol[i][j] {
					pieces++
				}
			}
		}

		fmt.Printf("Case #%d: %d %d\n", tc, N+plusPoints, pieces)
		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				if 0 < crossSol[i][j] || 0 < plusSol[i][j] {
					var ch byte
					if plusSol[i][j] != 0 && crossSol[i][j] != 0 { // != 0 means original sol add new sol
						ch = 'o'
					} else if plusSol[i][j] != 0 {
						ch = '+'
					} else {
						ch = 'x'
					}
					fmt.Printf("%c %d %d\n", ch, i+1, j+1)
				}
			}
		}
	}
}