技巧
df***r />
思路
抽象成二维数组。按照从上到下 从右往左的顺序去尝试每一个字母
注意剪枝和basecase的进位处理
实现
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) }