WustOJ 1575 Gingers and Mints(快速幂 + dfs )

1575: Gingers and Mints

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 24  Accepted: 13
[Submit][Status][Web Board]

Description

fcbruce
owns a farmland, the farmland has n * m grids. Some of the grids are
stones, rich soil is the rest. fcbruce wanna plant gingers and mints on
his farmland, and each plant could occupy area as large as possible. If
two grids share the same edge, they can be connected to the same area.
fcbruce is an odd boy, he wanna plant gingers, which odd numbers of
areas are gingers, and the rest area, mints. Now he want to know the
number of the ways he could plant.

Input

The first line of input is an integer T (T < 100), means there are T test cases.

For each test case, the first line has two integers n, m (0 < n, m < 100).

For next n lines, each line has m characters, ‘N‘ for stone, ‘Y‘ for rich soil that is excellent for planting.

Output

For each test case, print the answer mod 1000000007 in one line.

Sample Input

2
3 3
YNY
YNN
NYY
3 3
YYY
YYY
YYY

Sample Output

4
1

HINT

For the
first test case, there are 3 areas for planting. We marked them as A, B
and C. fcbruce can plant gingers on A, B, C or ABC. So there are 4 ways
to plant gingers and mints.

Source

武汉科技大学第二届移动互联网应用设计大赛(A类)暨华中地区程序设计竞赛专业组网络赛

Author

fcbruce

思路:

1.先用DFS求出联通块个数。

2.再根据数学知识 C{n,1} + C{n,3} + C{n,5} + ... = 2^(n-1) 用快速幂求出。

#include<cstdio>
#include<cstring>
using namespace std;

#define maxn 200
char pic[maxn][maxn];
int vis[maxn][maxn];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int n,m;

void dfs(int x, int y)
{
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(!vis[nx][ny] && pic[nx][ny] == ‘Y‘ && nx >= 0 && nx < n && ny >= 0 && ny < m)
        {
            vis[nx][ny] = 1;
            dfs(nx,ny);
        }
    }
}
int pow_mod(int a,int n,int m)
{

    if(n==0)
    return  1;
    int x=pow_mod(a,n/2,m);
    long long ans=(long long)x*x%m;
    if(n%2==1)
        ans=ans*a%m;
    return (int )ans;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        memset(vis, 0, sizeof vis);
        for(int i = 0; i < n; i++)
            scanf("%s", pic[i]);
        int cnt = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
            {
                if(!vis[i][j] && pic[i][j] == ‘Y‘)
                {
                    vis[i][j] = 1;
                    cnt++;
                    dfs(i,j);
                }
            }
            printf("%d\n",pow_mod(2,cnt-1,1000000007));
    }
    return 0;
}
时间: 04-17

WustOJ 1575 Gingers and Mints(快速幂 + dfs )的相关文章

hdu 1575 try a 矩阵快速幂

#include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<queue> #include<stack> #include<algorithm> #include<iostream> using namespace std; #define ll long long int const int m=9973; ll

矩阵快速幂——将运算推广到矩阵上HDU 1575

/* 本题的思路比较简单,就是将递推公式写出来,然后表达成为一个矩阵的形式 最后通过计算就可以得到一个符合题目要求的矩阵, 然后就是将矩阵上面所有的对角线元素相加 得到的结果即为所求的目标 */ #include<cstdio>  #include<cstring>  using namespace std;  const int maxn = 15;  #define mod 9973  int res[maxn][maxn];  int n;  void mul(int a[]

第三次周赛题解【并查集 KMP DFS BFS 快速幂】

问题 A: 一道签到题 时间限制: 2 Sec  内存限制: 128 MB 提交: 63  解决: 28 [提交][状态][讨论版] 题目描述 我想说这是一道签到题,意思就是本次测试中最水的一道,不过我这样说你真的愿意相信我吗?哈哈,题目是这样的给你一下小数,然后请告诉我分别告诉我这个小数的循环节的循环次数.循环节以及循环节长度 输入 输入包括多组测试数据每组测试数据1行,包括一个小数,小数的长度不超过200,小数大于0小于100 输出 分别输出这个小数的循环节的长度.循环节以及循环次数,中间以

HDU 1575 Tr A(矩阵快速幂)

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5537    Accepted Submission(s): 4161 Problem Description A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973. Input 数据的第一行是一个T,表示有T组数据.每组数据的第一行有n(2 <=

hdu 1575 求一个矩阵的k次幂 再求迹 (矩阵快速幂模板题)

Problem DescriptionA为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973. Input数据的第一行是一个T,表示有T组数据.每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据.接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容. Output对应每组数据,输出Tr(A^k)%9973. Sample Input22 21 00 13 999999991 2 34

hdoj 1575 Tr A 【矩阵快速幂】

Tr A Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3020    Accepted Submission(s): 2251 Problem Description A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973. Input 数据的第一行是一个T,表示有T组数据. 每组数据的第一行有

矩阵快速幂刷题系列

来源自http://blog.csdn.net/chenguolinblog/article/details/10309423 hdu 1575 Tr A Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5587    Accepted Submission(s): 4200 Problem Description A为一个方阵,则Tr

【66测试20161115】【树】【DP_LIS】【SPFA】【同余最短路】【递推】【矩阵快速幂】

还有3天,今天考试又崩了.状态还没有调整过来... 第一题:小L的二叉树 勤奋又善于思考的小L接触了信息学竞赛,开始的学习十分顺利.但是,小L对数据结构的掌握实在十分渣渣.所以,小L当时卡在了二叉树. 在计算机科学中,二叉树是每个结点最多有两个子结点的有序树.通常子结点被称作“左孩子”和“右孩子”.二叉树被用作二叉搜索树和二叉堆.随后他又和他人讨论起了二叉搜索树.什么是二叉搜索树呢?二叉搜索树首先是一棵二叉树.设key[p]表示结点p上的数值.对于其中的每个结点p,若其存在左孩子lch,则key

快速幂-(复习)

快速幂要用二分指数的办法来计算, 一般只用把结果取余就可以了 例题 NOIP2013提高组day2第一题 转圈游戏 读题可以知道本题就是求(10^k*m+x)%n 就求10^k%n 可以用记忆化搜索,记得不要dfs两次一样的,设个long long 保存 但也可用直接 用二进制来分解K 一下是最后一种代码 #include <iostream>#include<cstdio>using namespace std;long long n,m,x,k,a=10,ys=1;int ma