城堡 The Castle

2024-03-31 21:48

文章标签 城堡 castle

本文主要是介绍城堡 The Castle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

城堡 The Castle

洛谷P1457

在这里插入图片描述

唉这道题不是特别难就是要求输出太多无奈之下写了90行

在这里插入图片描述

算了今天在代码上写注释吧

#include <iostream>
using namespace std;
int n,m,cnt,area,marea=0,dir;
int w[55][55],f[55][55]; // w记录墙 f就是flag
int dx[4]={0,-1,0,1}; // 这个数组用来为x轴随时判断方向
int dy[4]={-1,0,1,0}; // 这个数组用来为y轴随时判断方向
int harea [2505]; // void dfs (int x,int y) // 深搜
{if (x<1 || y<1 || x>n || y>m || f[x][y]) return; // 如果越界就返回f[x][y]=cnt; // 判断这个屋子结束了harea[cnt]++; // 记录这个屋子的大小for (int i=0;i<=3;i++)if (!((w[x][y]>>i)&1)) dfs(x+dx[i],y+dy[i]); // 判断这个房间的上下左右
}
int main ()
{cin >> m >> n;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)cin >> w[i][j];for (int j=1;j<=m;j++) // 这里其实暴力就可以 不用非这么写for (int i=n;i>0;i--)if (f[i][j]==0) // 如果没有检测过{cnt++;// 房间数目++dfs (i,j); // 判断这个房间if (harea[cnt]>marea) // 如果这个房间的大小是目前最大的marea=harea[cnt]; // 记录下来}cout << cnt << endl; // 第一问cout << marea << endl; // 第二问int x=0,y=0;for (int j=1;j<=m;j++) // 优先选西和南{for (int i=n;i>0;i--){if ((w[i][j]>>1)&1) // 如果有北墙{if (f[i][j]!=f[i-1][j]) // 且不是同一房间{int a1 = harea[f[i][j]],a2=harea[f[i-1][j]]; // 分别记录两个房间的大小if (a1+a2>marea) // 如果加起来更大{marea=a1+a2; // 更新记录！x=i;y=j;dir=1; // 确定啦 就是你北墙！}}}if ((w[i][j]>>2)&1) // 如果有东墙{if (f[i][j]!=f[i][j+1]) // 且不是同一房间{int a1 = harea[f[i][j]],a2=harea[f[i][j+1]]; // 分别记录二个房间的大小if (a1+a2>marea) // 如果加起来更大{marea=a1+a2; // 更新记录！x=i;y=j;dir=2; // 确定啦 就是你东墙}}}}}cout << marea << endl; // 第三问cout << x  << " " << y << " ";if (dir==1)cout << "N" << endl; // 第四问elsecout << "E" << endl;return 0;}