2662: T5-推箱子
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
有一款推箱子游戏。游戏每一关由长度为 n 的字符“_”(空格)和“@”(箱子)组成初始状态，让当前所有箱子集中到一块即可过关。
在一个动作中，如果目标移动的位置存在并且是空的，你可以将任何箱子向左移动一个位置或向右移动一个位置。当前所有箱子一排好，即任意两个箱子之间都不存在空格，方可进入下一关。
此款游戏共有 t 关，确定通过每一关卡所需的最小移动次数。
在一个动作中，如果目标移动的位置存在并且是空的，你可以将任何箱子向左移动一个位置或向右移动一个位置。当前所有箱子一排好，即任意两个箱子之间都不存在空格，方可进入下一关。
此款游戏共有 t 关，确定通过每一关卡所需的最小移动次数。
输入
第一行：一个整数 t ,表示 t 个关卡。
接下来是 2t 行表示每一关初始情况。
一个整数 n， 表示当前可用位置情况
一个长度为 n 的字符串，只包含“_”(空格)和“@”(箱子)
接下来是 2t 行表示每一关初始情况。
一个整数 n， 表示当前可用位置情况
一个长度为 n 的字符串，只包含“_”(空格)和“@”(箱子)
输出
输出共 t 行，每一行表示通过每一关卡所需的最小移动次数。
样例输入 复制
3
6
@@_@__
3
_@_
10
@_@___@_@@样例输出 复制
1
0
9提示
样例解释：
@@@___ (最右边箱子向左移动1个单位)
_@_ (移动0次)
3 + 4 + 1 + 1 = 9 。左边第2个箱子向右移动3个单位、最左边箱子向右移动4个单位、 右边第2个箱子向左移动1个单位、最右边箱子向左移动1个单位
数据范围
对于 30% 的数据，1≤ t ≤10, 1≤ ∑ni≤ 103。
对于 60% 的数据，1≤ t ≤103, 1≤ ∑ni≤ 5∗105。
对于 100% 的数据，1≤ t ≤104, 1≤ ∑ni ≤106。
@@@___ (最右边箱子向左移动1个单位)
_@_ (移动0次)
3 + 4 + 1 + 1 = 9 。左边第2个箱子向右移动3个单位、最左边箱子向右移动4个单位、 右边第2个箱子向左移动1个单位、最右边箱子向左移动1个单位
数据范围
对于 30% 的数据，1≤ t ≤10, 1≤ ∑ni≤ 103。
对于 60% 的数据，1≤ t ≤103, 1≤ ∑ni≤ 5∗105。
对于 100% 的数据，1≤ t ≤104, 1≤ ∑ni ≤106。