房间问题.ppt

房间问题
张伊伦
C++
问题描述
下图是一张建筑平面图，编程计算： 1 、该建筑中有多少个房间： 2 、最大的房间有多大； 3 、拆除建筑中的某一堵墙，以形成一个尽可能大的房间。指出 该墙。该建筑分成 m ＊ n 个方块 (m ≤ 50 ， n ≤ 50) ，每个方块可有 0 ~ 4 堵墙 ) 。
样例的平面图如下：
struct room{int shang;int xia;int zuo;int you;int zh;;void zhang(){zh=1;};void cl(){if (j%2==1){zuo=1; j=j-1;}switch (j){case 2:shang=1;break;case 4:you=1;break;case 8:xia=1;break;case 6:{shang=1;you=1;};break;case 10:{shang=1;xia=1;};break;case 12:{you=1;xia=1;};break;case 14:{shang=1;you=1;xia=1;};break;}}
数据部分
标记
处理读入数据
定义room类型
算法
深搜(递归)
把每个方块看成一个点,如果两点之间没有墙,则递归相邻的点,遇墙返回;
枚举
枚举所有可能拆除的墙,每拆除一面墙,则调用一遍递归过程,并记录最大值
(递归)
把每个方块看成一个点,如果两点之间没有墙,则递归相邻的点,遇墙返回;
void dfs(room p)
();f++;
if ((==0)&&(d2!=0)){d2=d2-1;if (q[d1][d2].zh==0)dfs(q[d1][d2]);d2=d2+1; }
if ((==0)&&(d1!=a-1)){d1=d1+1;if (q[d1][d2].zh==0)dfs(q[d1][d2]);d1=d1-1; }
if ((==0)&&(d2!=s-1)){d2=d2+1;if (q[d1][d2].zh==0)dfs(q[d1][d2]);d2=d2-1; }
if ((==0)&&(d1!=0)){d1=d1-1;if (q[d1][d2].zh==0)dfs(q[d1][d2]);d1=d1+1;
Void Make1()
ifstream fin(“d:/”);fin>>a>>s;for (d1=0;d1<=a-1;d1++)for(d2=0;d2<=s-1;d2++){fin>>j;q[d1][d2].cl();} //处理读入数据for (d1=0;d1<=a-1;d1++)for(d2=0;d2<=s-1;d2++){if (q[d1][d2].zh!=1){ f=0;h++;dfs(q[d1][d2]);if (f>g) {g=f;}}}