题解洛谷P1457 【城堡 The Castle】

这道题，看似很烦，无从下手，但其实只要用位运算和联通快就能水过了呀。

首先，输入大意是把一个数拆成二进数的相加，分别表示 \((i,j)\) 东南西北是否有墙。\(1\) 表示西，\(2\) 表示北，\(4\) 表示东，\(8\) 表示南。

第一种方法，你可以写 \(15\) 个 \(\operatorname{if}\)，分别枚举 \(15\) 种情况，然后求出它的二进制拆分。

第二种比较简单的方法，我们可以尝试用位运算来解决。

先来了解一下位运算中的 \(\&\)。它做的是一种与运算，对于两个 \(2\) 进制，当它们的某一位都是 \(1\)，则返回 \(1\)，否则返回 \(0\)。

举个栗子：\(3\&11=0011\&1011=0011\)

好了，诸如 \(1,2,4,8……\) 这样的数，它们在二进制中都只能拆成\(0001,0010,0100,1000……\)。假如我们要知道某个数中能否拆成一个\(2^n\)，那我们只需要拿它的二进数与 \(2^n\) 的二进制进行比较。如果它们有共同的\(1\)，则说明 \(2^n\) 是其拆出来的一个数。

那么接下来，即可考虑设一个数组 \(a[i][j][k]\)，表示对于某个房间 \((i,j)\)，其 \(k\) 方向是否有墙。

注意 \(0\) 表示西方，\(1\) 表示北方，\(2\) 表示东方，\(3\) 表示南方。

const int dir[5][5]={

    {0,-1},{-1,0},{0,1},{1,0}//方向

};

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

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

    	int x;

	    cin>>x;

        if(x&1)a[i][j][0]=1;

		if(x&2)a[i][j][1]=1;

		if(x&4)a[i][j][2]=1;

		if(x&8)a[i][j][3]=1;

		//位运算，1表示有墙

	}

}

下面可以切入主程序了。

对于第一二问，题目是要求联通快的个数以及最大的联通快的面积。

这个很简单，我们用\(dfs\)遍历所有点。每个点扩展出他的所有联通快，并且记录最大的面积即可。

对于第三四问，题目是要我们找拆掉哪面墙才能使得新房间的大小尽可能大。

其实说白了还是枚举，我们要暴搜所有的墙。假如拆掉了 \((i,j)\) 北面的墙，则 \((i-1,j)\) 南面的墙也会被拆掉。假如拆掉了 \((i,j)\) 东面的墙，则 \((i+1,j)\) 西面的墙也会被拆掉。

故在拆墙的过程中，可能会影响到许多的房间，这是我们要特殊考虑的。

\(\operatorname{Code}:\)

#include<bits/stdc++.h>

using namespace std;

int n,m,a[60][60][10],h[60][60];

int sum,area,max_area;

int ansx,ansy,ansfx;

const int dir[5][5]={

    {0,-1},{-1,0},{0,1},{1,0}//方向

};

void dfs(int x,int y){

    h[x][y]=1,area++;

    for(int i=0;i<4;i++){

        if(a[x][y][i])continue;//有墙！

        int tx=x+dir[i][0];

        int ty=y+dir[i][1];//下一个点

        if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&h[tx][ty]==0){

            //未超边界且可以走

            dfs(tx,ty);

        }

    }

}

void find_(int x,int y,int fx){//查找联通快

    memset(h,0,sizeof(h));//清零！

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

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

            if(h[i][j])continue;

            area=0;

            dfs(i,j),sum++;//查找联通快

            if(area>max_area){

                max_area=area;//更新最大面积

                ansx=x,ansy=y,ansfx=fx;//记录坐标，方向

            }

        }

    }

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin>>m>>n;

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

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

            int x;

            cin>>x;

            if(x&1)a[i][j][0]=1;

            if(x&2)a[i][j][1]=1;

            if(x&4)a[i][j][2]=1;

            if(x&8)a[i][j][3]=1;

            //位运算，1表示有墙

        }

    }

    find_(0,0,0);

    cout<<sum<<endl;

    cout<<max_area<<endl;

    max_area=0;

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

        for(int i=n;i>=1;i--){

            for(int k=1;k<3;k++){

                if(a[i][j][k]==0)continue;

                a[i][j][k]=0;

                if(k==1)a[i-1][j][3]=0;

                if(k==2)a[i][j+1][0]=0;

                find_(i,j,k);

                a[i][j][k]=1;

                if(k==1)a[i-1][j][3]=1;

                if(k==2)a[i][j+1][0]=1;

            }

        }

    }

    cout<<max_area<<endl;

    char ansch;

    if(ansfx==1)ansch='N';

    else ansch='E';//判断方向

    cout<<ansx<<" "<<ansy<<" "<<ansch<<endl;

    return 0;

}

\(\operatorname{Update}\) \(\operatorname{On}\) \(\operatorname{2019.05.17}\)

巴特西

题解洛谷P1457 【城堡 The Castle】

最新文章

热门文章

巴特西

题解 洛谷P1457 【城堡 The Castle】

最新文章

热门文章

题解洛谷P1457 【城堡 The Castle】