Game on Chessboard
Time Limit: 12000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 88 Accepted Submission(s): 7
Problem Description
在一个 $n \times n$ 的棋盘中有若干个棋子，其中以左下角为 $(1,1)$，右上角为 $(n,n)$，棋子有白色和黑色两种颜色，其中位于 $(i,j)$ 的棋子有一个权值 $w_{i,j}$，每个格子上最多只有一个棋子。
每次你可以选择两个不同颜色的棋子并将这两个棋子同时消掉，但是需要保证在这两个棋子的左下方除了它们本身之外没有任何其他棋子，形式化地，设选定的两个棋子位置分别为 $(x_1,y_1), (x_2,y_2)$，则需要保证在 $(1,1) - (x_1,y_1)$ 这个子矩阵内只有 $(x_1,y_1)$ 处有棋子，$(x_2,y_2)$ 同理。则此次消除所需代价为两个棋子的权值差的绝对值 $|w_{x_1,y_1} - w_{x_2,y_2}|$。
但是考虑到可能不一定每次都能找到满足条件的两个棋子，所以你每次也花费若干法力让一个棋子凭空消失，但是被选择的棋子也必须满足“左下方除了它本身之外没有任何其他棋子”的限制。当然，你完全也可以在能选两个棋子配对的时候进行这个操作。则此次消除所需代价为即该棋子的权值。
现在你想将这些棋子全部消掉，并且想知道最少需要多少的法力值才能将这些棋子消掉。
每次你可以选择两个不同颜色的棋子并将这两个棋子同时消掉，但是需要保证在这两个棋子的左下方除了它们本身之外没有任何其他棋子，形式化地，设选定的两个棋子位置分别为 $(x_1,y_1), (x_2,y_2)$，则需要保证在 $(1,1) - (x_1,y_1)$ 这个子矩阵内只有 $(x_1,y_1)$ 处有棋子，$(x_2,y_2)$ 同理。则此次消除所需代价为两个棋子的权值差的绝对值 $|w_{x_1,y_1} - w_{x_2,y_2}|$。
但是考虑到可能不一定每次都能找到满足条件的两个棋子，所以你每次也花费若干法力让一个棋子凭空消失，但是被选择的棋子也必须满足“左下方除了它本身之外没有任何其他棋子”的限制。当然，你完全也可以在能选两个棋子配对的时候进行这个操作。则此次消除所需代价为即该棋子的权值。
现在你想将这些棋子全部消掉，并且想知道最少需要多少的法力值才能将这些棋子消掉。
Input
输入第一行一个正整数 $n(1 \le n \le 12)$，表示棋盘大小。
接下来 $n$ 行，每行一个长为 $n$ 的字符串，其中字符串由 'W','B','.' 组成。'W' 表示一个红色棋子，'B' 表示一个黑色棋子，'.' 表示没有棋子。
接下来 $n$ 行，每行 $n$ 个非负整数 $w_{i,j} (0 \le w_{i,j} \le 10^6)$，表示让位置 $(i,j)$ 所在棋子的权值，保证 $w_{i,j}$ 为正当且仅当棋盘上对应位置存在棋子。
样例输出
一个可能的方案如下:
第一步把 (1,1) 用 1 点法力消掉
第二步把 (1,2) 和 (2,1) 配对消掉，代价为 $|1-1|=0$
第三步把 (1,3) 用 1 点法力消掉
第四步把 (1,4) 和 (2,2) 配对消掉，代价为 $|1-1|=0$
第五步把 (2,3) 和 (3,1) 配对消掉，代价为 $|1-1|=0$
第六步把 (2,4) 和 (3,2) 配对消掉，代价为 $|1-1|=0$
第七步把 (3,3) 和 (4,1) 配对消掉，代价为 $|1-1|=0$
第八步把 (3,4) 和 (4,2) 配对消掉，代价为 $|1-1|=0$
第九步把 (4,3) 用 1 点法力消掉
接下来 $n$ 行，每行一个长为 $n$ 的字符串，其中字符串由 'W','B','.' 组成。'W' 表示一个红色棋子，'B' 表示一个黑色棋子，'.' 表示没有棋子。
接下来 $n$ 行，每行 $n$ 个非负整数 $w_{i,j} (0 \le w_{i,j} \le 10^6)$，表示让位置 $(i,j)$ 所在棋子的权值，保证 $w_{i,j}$ 为正当且仅当棋盘上对应位置存在棋子。
Hint
样例输出
一个可能的方案如下:
第一步把 (1,1) 用 1 点法力消掉
第二步把 (1,2) 和 (2,1) 配对消掉，代价为 $|1-1|=0$
第三步把 (1,3) 用 1 点法力消掉
第四步把 (1,4) 和 (2,2) 配对消掉，代价为 $|1-1|=0$
第五步把 (2,3) 和 (3,1) 配对消掉，代价为 $|1-1|=0$
第六步把 (2,4) 和 (3,2) 配对消掉，代价为 $|1-1|=0$
第七步把 (3,3) 和 (4,1) 配对消掉，代价为 $|1-1|=0$
第八步把 (3,4) 和 (4,2) 配对消掉，代价为 $|1-1|=0$
第九步把 (4,3) 用 1 点法力消掉
Output
输出仅一行一个非负整数，表示将所有棋子全部消掉最少需要的法力值。
Sample Input
4 WBB. BWBW WBWW BBBW 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output
3
Source
642ccpcQHD