#深度优先搜索 #博弈论
需要一点细节的博弈论好题。
## 题目大意
有 $3\times 3$ 的棋盘，第 $i$ 行第 $j$ 列上面的数为 $a_{i,j}$。高桥和奥吉轮流下棋，如果在下棋的过程中其中一个人有三个子连成了一条长度为 $3$ 线，那么这个人就直接赢了。如果到最后都没分出胜负，那么就按照下的位置上面的数的和为标准来判断。两个人都会选择最优策略。
## 思路
首先是这道题的中心思想，非常重要，一定要默念三遍：如果对面有一种下棋方法必输，那么我就是必赢的；如果对面所有的下棋方法都必赢，那么我就必输。
接下来，我们可以采用 $\mathcal O(9!)$ 的大爆搜，这就代表着，只要我们细心地对着上面的结论进行模拟，那么就可以一遍过！
## 代码
```kotlin
import java.util.*
val cin = Scanner(System.`in`)
const val n = 3
val a = Array(n + 1) { LongArray(n + 1) } // 位置上面的数
val f = Array(n + 1) { LongArray(n + 1) } // 每一个位置被谁给标记了
var s1 = 0L // 高桥的和
var s2 = 0L // 奥吉的和
fun check(): Long { // 判断那个人连成了一条线
for (i in 1..n) { // 遍历每一行和每一列
if (f[i][1] != 0L && f[i][1] == f[i][2] && f[i][2] == f[i][3]) { // 当前行的赢了
return f[i][1] // 返回赢了的人
} else if (f[1][i] != 0L && f[1][i] == f[2][i] && f[2][i] == f[3][i]) { // 当前列的赢了
return f[1][i] // 返回赢了的人
}
}
if (f[1][1] != 0L && f[1][1] == f[2][2] && f[2][2] == f[3][3]) { // 右斜线
return f[1][1]
} else if (f[1][3] != 0L && f[1][3] == f[2][2] && f[2][2] == f[3][1]) { // 左斜线
return f[1][3]
}
return 0L // 没有人赢
}
fun dfs(x: Long): Boolean { // 大爆搜环节
if (check() != 0L) { // 如果有人连成了一条线
return check() - 1L != x % 2L // 判断当前人是否输了
// 这里可能比较抽象
// 因为当前人还没有下棋，因此需要判断的是当前人有没有输
// check() - 1L：高桥赢了为 0，奥吉赢了为 1
// x % 2L：当前为高桥为 1，当前为奥吉为 0
// 需要使用不等于号，因为假设当前为奥吉，刚才高桥赢了，
// 那么表达式就等同于 0 != 0，则 false
}
if (x > 9) { // 没有决出胜负
return s2 > s1 // 按照得分来判断
// 注意需要反过来，因为
// 刚才下的是高桥，我们需要
// 判断奥吉有没有赢
}
var b = false // 判断对面有没有必输的可能
for (i in 1..n) { // 枚举行
for (j in 1..n) { // 枚举列
if (f[i][j] == 0L) { // 如果还没有被下
if (x % 2 != 0L) s1 += a[i][j] else s2 += a[i][j] // 累加到得分里面
f[i][j] = if (x % 2 != 0L) 1 else 2 // 打上标记，高桥为 1，奥吉为 2
b = b || !dfs(x + 1) // 继续搜索，看对面有没有必输的可能（这里可以剪枝）
if (x % 2 != 0L) s1 -= a[i][j] else s2 -= a[i][j] // 去掉加上的得分
f[i][j] = 0L // 清空标记
}
}
}
return b // 是否必赢
}
fun main() {
for (i in 1..n) {
for (j in 1..n) {
a[i][j] = cin.nextLong()
}
}
println(if (dfs(1)) "Takahashi" else "Aoki")
}
```