Skip to content

14108: 【原4108】N0 Chess N0 Life

题目

题目描述

author: 黄俊翔 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4108 ## Description

为了争夺人类最后一块国土——艾尔齐亚的王位,空与白这对兄妹必须在国王选拔战中战胜克拉米。尽管选拔战的项目是白绝不可能会输的国际象棋,但由于克拉米的背后有擅长魔法的森精灵撑腰,这场对决最终从棋艺对决变成了魔法象棋对决。然而在赛前,克拉米早已暗中命森精灵作弊加强了友方(黑方)棋子的能力;所幸的是空用自己的强大领导力逆转了局势,逼得克拉米只剩下最后寥寥几个棋子。

走投无路的克拉米再次利用了森精灵的魔法,黑方主教(bishop,国际象棋中象)突然搓起了大召唤术,在棋盘上召唤出无数的狂化教徒。每个格子中最多有一个教徒,教徒的攻击范围和主教类似都是斜着的,但是长度只有一格,也就是只能攻击对角相邻的方格。此外如果有两个教徒站在两个对角相邻的方格中,且不存在另一个教徒同时与这两个教徒相邻的话,则这两个发狂的教徒也会相互攻击(即L型或者田型的放置都是合法的);黑方主教清楚这一点,所以他不会这样放置两个教徒。

面对这样的危机,空询问白方主教会不会一些厉害的膜法可以一发带走对面的所有教徒。年长而身经百战的白方主教表示自己的确可以通过上位膜法时间操纵使得黑方所有教徒的剩余生命直接清0,真正实现No Chess No Life;但是如果不事先预知到敌方教徒所有可能的合法摆放方式,就可能会发动失败。空说这个简单,于是在白背后插了两根电线将她Cosplay成休比,然后计算了1s,便算出了敌方教徒在棋盘上所有可能的摆放方式,让白方主教成功施放出膜法,顺利击败了克拉米。考虑到同学们的计算机没有休比那么bug的算力,所以同学们只要输出可能的摆放方式总数\(mod\ 1000000007\)的值就可以啦。

Input Format

第一行一个整数\(T\),为数据组数。

接下来\(T\)行,每组数据一行两个数字\(N,M\),代表棋盘的行数和列数。此时这块棋盘区域上是一个棋子都没有的,黑方主教可以在这块区域上召唤任意多的教徒,一个都不召唤和放满这块区域也是两种合法的摆放方案(放满为什么是合法的可以再读一遍之前合法的定义)。

Output Format

有\(T\)组输出,对应T组输入。

每组数据输出一行一个数字,代表教徒在这块棋盘上可能的摆放方式总数\(mod\ 1000000007\)的值。

Sample Input

2
2 3
1 1

Sample Output

50
2

Data Range

对于\(30\%\)的数据,\(N \le 3\)。

对于\(70\%\)的数据,\(N \le 40\)。

对于\(100\%\)的数据,\(1 \le T \le 5, 1 \le N \le 10^9, 1 \le M \le 7\)。

注:这是魔法象棋的棋盘,所以棋盘长成长条形也是很正常的。

本题时间限制2s。

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
char map[1005][1005];
int minx[1005][1005],qx[1000011],qy[1000011];
int sx,sy,head,tail,m,n,now,xnow,ynow,ex,ey;
void update(int value,int x,int y)
{
    if (map[x][y]=='#') return;
    if ((map[x][y]=='$'||map[x][y]=='.')&&(minx[x][y]==0)) {
        minx[x][y] = value;
        qx[tail] = x;
        qy[tail] = y;
        tail++;
    }
}
int main() {
    scanf("%d%d",&m,&n);
    for (int i=0;i<m;++i)
    {
        scanf("%s",map[i]);
        for (int j=0;j<n;++j) {
            if (map[i][j] == '@') {
                sx = i;
                sy = j;
            }
            if (map[i][j] == '$'){
                ex = i;
                ey = j;
            }
        }
    }
    qx[0]=sx;
    qy[0]=sy;
    head=0;
    tail=1;
    while (head<tail)
    {
        now=minx[qx[head]][qy[head]];
        xnow=qx[head];
        ynow=qy[head];
        if (xnow>=1) update(now+1,xnow-1,ynow);
        if (ynow>=1) update(now+1,xnow,ynow-1);
        if (xnow<m-1) update(now+1,xnow+1,ynow);
        if (ynow<n-1) update(now+1,xnow,ynow+1);
        head++;
        if (minx[ex][ey]!=0) break;

    }
    if (!minx[ex][ey]) printf("%d",-1);
    else printf("%d",minx[ex][ey]);
    return 0;
}