ZHK

ZHK

一只叫ZHK的蒟蒻为了RP而战

题解 P1457 【城堡 The Castle】

posted on 2019-05-07 21:16:36 | under 题解 |

博客园体验更佳

来讨论区大摇大摆地逛了一圈后,我发现竟然大家的代码

都很长

然而代码真的要写那么长吗


首先,来分析问题,1,2,4,8,这些数显然是有特点的,也许你已经想到了没错,它们都是2的次方数。

1是2的0次方

2是2的1次方

4是2的2次方

8是2的3次方

知道这个就好办了,用什么呢?没错是位运算,哈哈!

1的二进制是1

2的二进制是10

4的二进制是100

8的二进制是1000

于是,就得出了以下代码:

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;

大家也看到了,我用了一个3维数组,a[55][55][4]。

看到这道题,我首先想到的是宽搜(宽度优先搜索),用数组模拟,这道题的数据范围不大,用数组完全可能。

上代码:

#include <bits/stdc++.h>//用万能头文件开始了代码
using namespace std;//命名空间
int n,m,h[55][55],a[55][55][4],s,ans,z1,z2;
int q1[10010],q2[10010],f[10010];
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
char z3;
string z="WNEA";
int main(){
    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;//位运算
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!h[i][j]){
                int front=0,rear=1,sum=1;
                q1[1]=i;
                q2[1]=j;
                h[i][j]=++s;
                while(front<rear){//开始宽搜
                    front++;
                    int x=q1[front],y=q2[front];
                    for(int k=0;k<=3;k++){
                        int tx=x+dx[k],ty=y+dy[k];
                        if(tx>0&&tx<=n&&ty>0&&ty<=m&&!h[tx][ty]&&!a[x][y][k]){
                            h[tx][ty]=s;
                            sum++;
                            q1[++rear]=tx;
                            q2[rear]=ty;
                        }
                    }
                }ans=max(ans,sum);
                f[s]=sum;//记录编号s的房间的间数
            }
    cout<<s<<endl<<ans<<endl;
    for(int j=1;j<=m;j++)//这里有坑
        for(int i=n;i>=1;i--)//这里有坑
            for(int k=1;k<=2;k++)
                if(a[i][j][k]){
                    int tx=i+dx[k],ty=j+dy[k];
                    int x=f[h[tx][ty]]+f[h[i][j]];//活用数组下标
                    if(x>ans&&h[tx][ty]!=h[i][j]){//一定要注意h[tx][ty]!=h[i][j],有时候尽管有墙,但能通过别的房间,达到这个房间。(考虑要周全)
                        ans=x;
                        z1=i;
                        z2=j;
                        z3=z[k];
                    }
                }
    cout<<ans<<endl<<z1<<" "<<z2<<" "<<z3;
    return 0;//华丽结束
}