深搜代码研读--城堡

题目标题:城堡

题目链接:

http://d1kt.cn/course/mod/programming/view.php?id=2465

AC代码欣赏:

  1. #define MAX 51//字符串替换
  2. #define loop for(i=1;i<=m;i++) for(j=1;j<=n;j++)
  3. #include <fstream>
  4. using namespace std;
  5.  
  6. int m,n,f[MAX][MAX],area[MAX*MAX],wall[MAX][MAX],lim=(1<<10)-1;
  7. //f[][]每个小房间填充的颜色变量;area[]房间的面积;
  8. //房间个数应该和颜色种类一致;wall[][]存墙值
  9. ifstream fin("castle.in");
  10. ofstream fout("castle.out");
  11.  
  12. int init()//初始化
  13. {
  14. int i,j,k,w;
  15. for(i=0;i<MAX;i++)
  16. for(j=0;j<MAX;j++)
  17. {
  18. f[i][j]=0;
  19. wall[i][j]=0;//初始全有墙,不通
  20. }
  21. for(i=0;i<MAX*MAX;i++)area[i]=0;
  22. loop//i,j <= m,n
  23. fin>>wall[i][j];
  24. return 0;
  25. }
  26.  
  27. int flood_fill(int i,int j,int c)//用颜色c填充单位(i,j)
  28. {
  29. if(f[i][j]==0)//如果单位i,j尚未填充任何颜色
  30. {
  31. f[i][j]=c;//填入颜色
  32. area[c]++;//填入该类颜色的区域面积加1
  33. //如果(i,j)单位四面分别无墙,则用color尝试填充四面单位
  34. int t=wall[i][j]^lim;
  35. //wall[][]和全1相异或,相当于取反,有墙的位变0,无墙变1
  36. //从而t&1==1说明西无墙,其他同理
  37. if(t&1)flood_fill(i,j-1,c);//W
  38. if(t&2)flood_fill(i-1,j,c);//N
  39. if(t&4)flood_fill(i,j+1,c);//E
  40. if(t&8)flood_fill(i+1,j,c);//S
  41. }
  42. return 0;
  43. }
  44.  
  45. int main()
  46. {
  47. int i,j,max=0,maxr=0,maxi=0,maxj=0,color=0;
  48. char maxd;//方向字符W,N,E,S
  49. //m:行数;n:列数;num:房间总数;max:最大房间面积;
  50. //maxr:拆掉某堵墙后最大房间面积;
  51. //maxi,maxj:拆掉那堵墙的南邻单位的北墙或西邻单位的东墙的行号和列号;
  52. //color颜色变量;
  53. fin>>n>>m;//读入房间列数和行数m行n列
  54. init();
  55. color=0;//准备颜色
  56. loop
  57. {
  58. if(f[i][j]==0)
  59. {
  60. color++;//换一种颜色
  61. flood_fill(i,j,color);//用颜色color填充(i,j)单元
  62. if(area[color]>max)max=area[color];
  63. //如果颜色color填充的房间面积较大的话,更新最大房间面积变量
  64. }
  65. }
  66. fout<<color<<endl;//房间数量和颜色种类一致
  67. fout<<max<<endl;
  68. //拆墙思路:
  69. //(1)某墙两边的单位填充不同颜色,即属于不同房间。
  70. //(2)如果两房间之和比当前最大值大,则记录该墙
  71. //(3)由于题目要求用某墙南邻单位的北墙或西邻单位的东墙表示该墙
  72. //有多个最优解时,按照西为第一关键字,南为第二关键字的原则进行
  73. //比如:某单位的北墙和东墙最优,我们选择北墙,因为北墙重心靠西
  74. //东西相邻两单位的北墙最优,我们选择西单位北墙
  75. //南北相邻两单位的东墙最优,我们选择南墙,因为他们平行无法按靠西进行
  76. //总之为了和"靠西靠南"原则一致
  77. //我们采取从左下角,从南到北,从东到西的次序枚举每个房间
  78. //在单位的层面上保证靠西靠南选取最优的原则
  79. //再者,我们枚举某单位的墙时我们只需枚举北墙和东墙,且先北墙后东墙
  80. //因为:
  81. //(1)最左下的单位西墙和南墙、第一列的西墙、最后一行的南墙都是围墙不必枚举
  82. //其它单位的西墙和南墙又是其它单位的东墙和北墙,我们已在到达给单位之前枚举过
  83. //(2)先北墙后东墙的顺序也保证了西墙优先原则
  84. for(j=1;j<=n;j++)//自西向东,lie
  85. for(i=m;i>=1;i--)//自南向北,hang
  86. {
  87. //判断北墙
  88. //(1)如果该单位北面还有单位(2)两单位分属不同房间
  89. //(3)两单位所属的两房间面积之和大于当前最大值
  90. if((i-1>0)&&(f[i][j]!=f[i-1][j])&&(area[f[i][j]]+area[f[i-1][j]]>maxr))
  91. {
  92. //如果当前墙较优则记录信息
  93. maxr=area[f[i][j]]+area[f[i-1][j]];
  94. maxi=i; maxj=j; maxd='N';
  95. }
  96. //判断东墙
  97. //(1)如果该单位东面还有单位(2)两单位分属不同房间
  98. //(3)两单位所属的两房间面积之和大于当前最大值
  99. if((j+1<=n)&&(f[i][j]!=f[i][j+1])&&(area[f[i][j]]+area[f[i][j+1]]>maxr))
  100. {
  101. //如果当前墙较优则记录信息
  102. maxr=area[f[i][j]]+area[f[i][j+1]];
  103. maxi=i; maxj=j; maxd='E';
  104. }
  105. }
  106. fout<<maxr<<endl<<maxi<<' '<<maxj<<' '<<maxd<<endl;
  107. fin.close();
  108. fout.close();
  109. return 0;
  110. }
最后修改: 2013年05月1日 星期三 11:22