算法1

(DFS)

代码比较长直接说思路吧。

1.对于找房间总数和房间面积,可以搜索每一个连通块记录一下每个联通快的面积以及房间数.
2.如何找到最大房间数？
(1)开一个二维数组记录每一个格子属于哪个房间.
(2)再开一个一维数组记录每个连通块的面积.
(3)遍历所有点,当两个点之间有墙并且不是边界并且不在同一个连通块内,则将两个连通块的面积相加取最大值.
3.如何知道拆哪面墙?
(1)将2.中的(3)中的这面墙与答案记录的比较一下即可。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1e3;

int n,m;
int map1[N][N];
int st[N][N];
int rooms=1,maxv;//rooms表示房间数，maxv表示拆之前最大房间面积
int area[N],id[N][N];//area表示每个连通块的面积,id表示当前的格子属于哪个连通块
int max1=0;//max1表示拆之后最大房间面积

struct node
{
    int x,y;
    char z;
}res;

int t=0;
void dfs(int x,int y)
{
    t++;
    id[x][y]=rooms;
    maxv=max(maxv,t);
    st[x][y]=1;
    if((map1[x][y]>>0&1)==0&&!st[x][y-1]) dfs(x,y-1); 
    if((map1[x][y]>>1&1)==0&&!st[x-1][y]) dfs(x-1,y);
    if((map1[x][y]>>2&1)==0&&!st[x][y+1]) dfs(x,y+1);
    if((map1[x][y]>>3&1)==0&&!st[x+1][y]) dfs(x+1,y);

    return ;
}

int main()
{
    cin>>m>>n;
    node res;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) cin>>map1[i][j];

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) if(!st[i][j]) {dfs(i,j),area[rooms]=t,rooms++,t=0;}

    ///下面这部分是解决移除哪面墙能够获得最大面积以及拆完后最大面积


    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
    if((map1[i][j]>>2&1)&&id[i][j+1]&&id[i][j+1]!=id[i][j]) //东边有墙且不是边界且不与当前格子连通
    {
      //  max1=max(max1,area[id[i][j+1]]+area[id[i][j]]);
      if(max1<=area[id[i][j+1]]+area[id[i][j]])
       {
           if(max1==area[id[i][j+1]]+area[id[i][j]]) 
           {
               if(j>res.y) continue;   //是否更靠西
               if(j==res.y&&i<res.x) continue; //是否更靠南
               if(i==res.x&&j==res.y&&res.z=='N') continue;//是否是北面
           }
           max1=area[id[i][j+1]]+area[id[i][j]];
           res={i,j,'E'};
       }
    }
     if((map1[i][j]>>1&1)&&id[i-1][j]&&id[i-1][j]!=id[i][j]) //北边有墙且不是边界且不与当前格子连通
    {
      //  max1=max(max1,area[id[i-1][j]]+area[id[i][j]]);
       if(max1<=area[id[i-1][j]]+area[id[i][j]])
       {
             if(max1==area[id[i-1][j]]+area[id[i][j]]) 
           {
              if(j>res.y) continue;   //是否更靠西
               if(j==res.y&&i<res.x) continue; //是否更靠南
               if(i==res.x&&j==res.y&&res.z=='N') continue;//是否是北面
           }

           max1=area[id[i-1][j]]+area[id[i][j]];
           res={i,j,'N'};
       }
    }
    if((map1[i][j]>>3&1)&&id[i+1][j]&&id[i+1][j]!=id[i][j]) //南边有墙且不是边界且不与当前格子连通
    {
       // max1=max(max1,area[id[i+1][j]]+area[id[i][j]]);
       if(max1<=area[id[i+1][j]]+area[id[i][j]])
       {
             if(max1==area[id[i+1][j]]+area[id[i][j]]) 
           {
               if(j>res.y) continue;   //是否更靠西
               if(j==res.y&&i<res.x) continue; //是否更靠南
               if(i==res.x&&j==res.y&&res.z=='N') continue;//是否是北面
           }

           max1=area[id[i+1][j]]+area[id[i][j]];
           res={i,j,'S'};
       }
    }
     if((map1[i][j]>>0&1)&&id[i][j-1]&&id[i][j-1]!=id[i][j]) //西边有墙且不是边界且不与当前格子连通
    {
       // max1=max(max1,area[id[i][j-1]]+area[id[i][j]]); 
       if(max1<=area[id[i][j-1]]+area[id[i][j]])
       {

             if(max1==area[id[i][j-1]]+area[id[i][j]]) 
           {
               if(j>res.y) continue;   //是否更靠西
               if(j==res.y&&i<res.x) continue; //是否更靠南
               if(i==res.x&&j==res.y&&res.z=='N') continue;//是否是北面
           }

           max1=area[id[i][j-1]]+area[id[i][j]];
           res={i,j,'W'};
       }
    }
    }

     cout<<rooms-1<<'\n'<<maxv<<'\n';
    cout<<max1<<'\n';
    cout<<res.x<<" "<<res.y<<" "<<res.z;

    return 0;
}