Game with Strings

题意翻译

## 题意翻译 给定一个 $n\times n$ 的表格，表格的每个位置都填写有一个小写字母，从上到下，行号依次为 $1$ 至 $n$ ，从左到右，列号依次为 $1$ 到 $n$，第 $i$ 行第 $j$ 列的字母我们用 $T_{i,j}$ 表示。 我们定义长度为 $1$ 的“好” 字符串 $s$ 为 $T_{1,1}$，我们假设长度为 $k$ 的“好”字符串为 $T_{r_1,c_1}+T_{r_2,c_2}+...+T_{r_k,c_k}$，则 $T_{r_1,c_1}+T_{r_2,c_2}...T_{r_k,c_k}+T_{r_k+1,c_k}$ 或者 $T_{r_1,c_1}+T_{r_2,c_2}...T_{r_k,c_k}+T_{r_k,c_k+1}$ 也是“好”字符串。 现有一空串，有两人轮流挑选字母，从末尾加入该串，并且必须保证该串在任意时刻都是“好”字符串，经过 $2n-1$ 次操作后 - 如果该串中 $a$ 的个数比 $b$ 多，则第一个人获胜； - 如果该串中 $a$ 的个数比 $b$ 少，则第二个人获胜； - 如果该串中 $a$ 的个数与 $b$ 的个数相等，则平局。 请输出最终结果。 ### 输入格式 第一行为一个整数 $1\le n\le 20$。 接下来 $n$ 行每行为一个长度为 $n$ 的只包含小写字母的字符串。 ### 输出格式 如果第一个人获胜，输出 "FIRST"；如果第二个人获胜，输出 "SECOND"；如果平局，输出 "DRAW"。

题目描述

Given an $ n×n $ table $ T $ consisting of lowercase English letters. We'll consider some string $ s $ good if the table contains a correct path corresponding to the given string. In other words, good strings are all strings we can obtain by moving from the left upper cell of the table only to the right and down. Here's the formal definition of correct paths: Consider rows of the table are numbered from 1 to $ n $ from top to bottom, and columns of the table are numbered from 1 to $ n $ from left to the right. Cell $ (r,c) $ is a cell of table $ T $ on the $ r $ -th row and in the $ c $ -th column. This cell corresponds to letter $ T_{r,c} $ . A path of length $ k $ is a sequence of table cells $ [(r_{1},c_{1}),(r_{2},c_{2}),...,(r_{k},c_{k})] $ . The following paths are correct: 1. There is only one correct path of length $ 1 $ , that is, consisting of a single cell: $ [(1,1)] $ ; 2. Let's assume that $ [(r_{1},c_{1}),...,(r_{m},c_{m})] $ is a correct path of length $ m $ , then paths $ [(r_{1},c_{1}),...,(r_{m},c_{m}),(r_{m}+1,c_{m})] $ and $ [(r_{1},c_{1}),...,(r_{m},c_{m}),(r_{m},c_{m}+1)] $ are correct paths of length $ m+1 $ . We should assume that a path $ [(r_{1},c_{1}),(r_{2},c_{2}),...,(r_{k},c_{k})] $ corresponds to a string of length $ k $ : $ T_{r1},c_{1}+T_{r2},c_{2}+...+T_{rk},c_{k} $ . Two players play the following game: initially they have an empty string. Then the players take turns to add a letter to the end of the string. After each move (adding a new letter) the resulting string must be good. The game ends after $ 2n-1 $ turns. A player wins by the following scenario: 1. If the resulting string has strictly more letters "a" than letters "b", then the first player wins; 2. If the resulting string has strictly more letters "b" than letters "a", then the second player wins; 3. If the resulting string has the same number of letters "a" and "b", then the players end the game with a draw. Your task is to determine the result of the game provided that both players played optimally well.

输入输出格式

输入格式

The first line contains a single number $ n $ $ (1<=n<=20) $ . Next $ n $ lines contain $ n $ lowercase English letters each — table $ T $ .

输出格式

In a single line print string "FIRST", if the first player wins, "SECOND", if the second player wins and "DRAW", if the game ends with a draw.

输入输出样例

输入样例 #1

2
ab
cd

输出样例 #1

DRAW

输入样例 #2

2
xa
ay

输出样例 #2

FIRST

输入样例 #3

3
aab
bcb
bac

输出样例 #3

DRAW

说明

Consider the first sample: Good strings are strings: a, ab, ac, abd, acd. The first player moves first and adds letter a to the string, as there is only one good string of length $ 1 $ . Then the second player can add b or c and the game will end with strings abd or acd, correspondingly. In the first case it will be a draw (the string has one a and one b), in the second case the first player wins. Naturally, in this case the second player prefers to choose letter b and end the game with a draw. Consider the second sample: Good strings are: x, xa, xay. We can see that the game will end with string xay and the first player wins.