洛谷 P6582 【座位调查】

这道题就两个步骤：

1.找联通块个数：判断是否符合标准并且找联通块个数

我用的广搜实现的，思路挺简单的：

先找一个联通块的端点，根据题中的定义，一个联通块的端点，周围所不是座位的个数（指上下左右），只有3个，或者4个（只有一个点的情况），对这个点进行搜索，标记，然后扩展，遇到下一个座位，就走，走过就标记，并对联通块计数的加一，最后返回走的联通块的座位数。

那么，如何判断这不是正确的教室呢？ 因为我们对搜过的都进行了标记，所以我们可以判断有没有是座位却没有被标记的情况，因为只有有端点的才能是符合标准的，没有对这一块进行搜索，那就是没有端点，也就不符合了。又因为我们从端点开始搜索的，那就说明每一个点能扩展的点，就只有一个点（本来应该是两个的，但是因为前一个点被标记了，也不能走，相当于只能扩展一个），我们可以进行统计每一个点能扩展的点，如果大于1，就也是错的。

2.对方法数目进行计算：利用乘法原理

啊本人不会画图就手打了吧

对于这一块的话OOOOOOO ，第一个可以填k个学校，那么后面一个就只能填k-1学校，后面的也是，以此类推，可以得到每一个联通块的方法数目为： k*(s-1)^(k-1) ，其中size为联通块大小，然后对于所有联通块一起的方法书，也一样，全乘起来就okk。

剩下的细节之类的都在代码里面了，码代上上代码：

#include <bits/stdc++.h>

using namespace std;

long long dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , -1 , 0 , 1};	//上下移动

long long n , m , k , sum , p = 998244353;	//sum是联通块个数

long long s[1000010];	//存储每一个联通块的大小

char a[1010][1010];	//存储图

bool f;	//判断是否座位只联通一个座位

bool vis[1010][1010];	//标记

struct node{

    long long c , d;

};

long long ksm(long long x , long long y){	//快速幂，怕超时，没去试pow（x，y）会不会超时

    long long ret = 1;

    y %= p;

    x %= p;

    while(y){

        if(y % 2 == 1){

            ret = ret * x;

            ret %= p;

        }

        x = x % p * x % p;

        x %= p;

        y /= 2;

    }

    return ret;

}

long long pd(long long x , long long y){	//统计周围不是座位的个数

    long long sssum = 0;

    if(a[x + 1][y] != 'O') sssum++;

    if(a[x - 1][y] != 'O') sssum++;

    if(a[x][y + 1] != 'O') sssum++;

    if(a[x][y - 1] != 'O') sssum++;

    return sssum;

}

long long bfs(long long x , long long y){	//广搜

    long long t = 1;

    queue<node> q;

    node nod;

    nod.c = x;

    nod.d = y;

    q.push(nod);

    node now;

    vis[x][y] = 1;

    while(!q.empty()){

        now = q.front();

        q.pop();

        long long tt = 0;

        for(int v = 0; v <= 3; v++){

            int nx = now.c + dx[v] , ny = now.d + dy[v];

            if(!vis[nx][ny] && a[nx][ny] == 'O'){

                tt++;	//统计这个点能扩展的点的个数

                t++;

                vis[nx][ny] = 1;

                nod.c = nx;

                nod.d = ny;

                q.push(nod);

            }

        }

        if(tt > 1){	//大于一个就说明不符合要求，并且不能用不等于，因为最后一个点是不能扩展的，就是0，但是合法

            f = true;

            return 0;	//不符合直接返回

        }

    }

    return t;

}

int main(){

    cin >> n >> m >> k;

    for(int i = 1; i <= n + 5; i++)

        for(int j = 1; j <= m + 5; j++) a[i][j] = 'X';	//初始化

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= m; j++) cin >> a[i][j];

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= m; j++){

            if(a[i][j] == 'O' && !vis[i][j]){	//找端点。为什么有vis？因为一个联通块有两个端点我们只需要搜索一次就OK

                int ha = pd(i , j);

				if(ha < 3) continue;	//不是端点

                f = false;

                sum++;	//块数加一

                s[sum] = bfs(i , j);

                if(f){	//不符合条件

                    cout << 0;

                    return 0;

                }

            }

        }

    for(int i = 1; i <= n; i++)	//找没搜过却是座位的情况，也是错误的

    	for(int j = 1; j <= m; j++)

    		if(a[i][j] == 'O' && !vis[i][j]){

    			cout << 0;

                return 0;

			}

    long long ans = 1;

    k %= p;

    for(int i = 1; i <= sum; i++){

        ans *= k % p * ksm((k - 1) , s[i] - 1) % p;	//记得每一次都mod一下，不然会只有30分的，别问我怎么知道的，调了半天的

        ans %= p;

    }

    cout << ans % p;

    return 0;

}

/*

7 7 99

XOOXOOO

XOXXXXO

XOOXOXO

XXXXOXO

XOOXOOO

XXOXXXX

XOOXOOO

*/

啊就这么多了，一道不错的搜索题

巴特西

洛谷 P6582 【座位调查】

最新文章

热门文章