题解 | #[NOIP2004]虫食算#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
)

func init() {
	for i := 0; i < 30; i++ {
		vis[i] = -1
	}
}

var (
	vis     = [30]int{}  // 字母对应用到的数字
	numused = [30]bool{} // 每个数字是否已经使用过了
)

func dfs(expressions []string, row, col, n, step int) {
	if col < 0 {
		if step != 0 {
			return
		}

		for i := 0; i < n-1; i++ {
			Printf("%d ", vis[i])
		}
		Printf("%d\n", vis[n-1])
		return
	}
	// 剪枝
	for i := 0; i < col; i++ {
		x := vis[expressions[0][i]-'A']
		y := vis[expressions[1][i]-'A']
		z := vis[expressions[2][i]-'A']
		if x == -1 || y == -1 || z == -1 {
			continue
		}
		 if (x+y)%n == z || (x+y+1)%n == z {
			continue
		} else {
			return
		}
	}

	if vis[expressions[row][col]-'A'] != -1 { // 该字母已经被赋值了
		if row == 2 { // 最后一行
			subtotal := vis[expressions[0][col]-'A'] + vis[expressions[1][col]-'A'] + step
			if subtotal%n != vis[expressions[2][col]-'A'] {
				return
			}
			dfs(expressions, 0, col-1, n, subtotal/n)
		} else { // 不是最后一行
			dfs(expressions, row+1, col, n, step)
		}
	} else { // 该字母未被赋值
		for i := n - 1; i >= 0; i-- {
			if numused[i] {
				continue
			}
			if row == 2 { // 最后一行
				subtotal := vis[expressions[0][col]-'A'] + vis[expressions[1][col]-'A'] + step
				if i != subtotal%n {
					continue 
				}
				numused[i] = true
				vis[expressions[row][col]-'A'] = i
				dfs(expressions, 0, col-1, n, subtotal/n)
				vis[expressions[row][col]-'A'] = -1
				numused[i] = false
			} else { // 不是最后一行
				numused[i] = true
				vis[expressions[row][col]-'A'] = i
				dfs(expressions, row+1, col, n, step)
				vis[expressions[row][col]-'A'] = -1
				numused[i] = false
			}
		}
	}

}

func NC16665(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var N int
	Fscan(in, &N)
	expressions := make([]string, N)
	for i := 0; i < N; i++ {
		Fscan(in, &expressions[i])
	}
	dfs(expressions, 0, N-1, N, 0)

}

func main() {
	NC16665(os.Stdin, os.Stdout)
}