题目大意：
给出一个地图，要求计算有多少个房间、最大房间的面积、删除哪一面墙会使合并房间的面积最大。
思路：
比较麻烦的搜索题，主要思路是用深搜计算每个房间的面积，时间复杂度属于O(n)级别。
代码：
1 | /* |
2 | ID: lujunda1 |
3 | LANG: C++ |
4 | PROG: castle |
5 | */ |
6 | #include<iostream> |
7 | #include<stdio.h> |
8 | using namespace std; |
9 | int n,m,map[51][51],size[51][51],num[51][51]; |
10 | //map[][]用于存储围墙信息。 |
11 | //size[i][j]的含义为(i,j)所处房间的大小。 |
12 | //num[i][j]的含义为(i,j)所处房间的编号。 |
13 | bool mark[51][51]; |
14 | //深搜时对访问过的位置进行标记。 |
15 | bool range(int i,int j) |
16 | //判断(i,j)是否超界。 |
17 | { |
18 | if(i>=1&&i<=n&&j>=1&&j<=m) |
19 | return true; |
20 | return false; |
21 | } |
22 | int dfs(int i,int j) |
23 | //深搜，用于计算房间面积。 |
24 | { |
25 | if(!range(i,j)||mark[i][j]) |
26 | //判断是否超界或已访问过。 |
27 | return 0; |
28 | mark[i][j]=true; |
29 | int sum=0; |
30 | for(int dir=0;dir<4;dir++) |
31 | if((map[i][j]>>dir)%2==0) |
32 | //把每个位置上的围墙数据表示成一个4位二进制，可以发现每一位都对应一个方向的墙。 |
33 | sum+=dfs(i+(dir-2)%2,j+(dir-1)%2); |
34 | //(i+(dir-2)%2,j+(dir-1)%2)表示与(i,j)一墙之隔的位置的坐标。 |
35 | return sum+1; |
36 | } |
37 | void updata(int i,int j,int val,int order) |
38 | //由于深搜只能将完整面积返回到房间中第一个被访问的位置上，所以需要通过更新操作更新所有位置的size信息。 |
39 | //val表示(i,j)所处房间的大小。 |
40 | //order表示(i,j)所处房间的编号。 |
41 | { |
42 | if(!range(i,j)||size[i][j]) |
43 | return; |
44 | size[i][j]=val; |
45 | num[i][j]=order; |
46 | for(int dir=0;dir<4;dir++) |
47 | if((map[i][j]>>dir)%2==0) |
48 | updata(i+(dir-2)%2,j+(dir-1)%2,val,order); |
49 | } |
50 | void get_size() |
51 | //通过updata()和dfs()对size[][]进行赋值。 |
52 | { |
53 | int total=0,max=0; |
54 | //total用于记录方案总数。 |
55 | //max用于记录房间面积最大值。 |
56 | for(int i=1;i<=n;i++) |
57 | for(int j=1;j<=m;j++) |
58 | if(!mark[i][j]) |
59 | { |
60 | updata(i,j,dfs(i,j),++total); |
61 | max=max>size[i][j]?max:size[i][j]; |
62 | } |
63 | printf("%d\n%d\n",total,max); |
64 | } |
65 | void remove_wall() |
66 | //找到题目所要求的墙，并记录新合并的房间的面积。 |
67 | { |
68 | int max=0,wall_y,wall_x; |
69 | //合并房间面积的最大值。 |
70 | //wall_y、wall_x表示墙所在位置的纵横坐标。 |
71 | char wall,wall_order[4]={'W','N','E','S'}; |
72 | //wall存储墙的方向字符。 |
73 | //关于墙的方向的搜索优先级对应的字符。 |
74 | for(int j=1;j<=m;j++) |
75 | for(int i=n;i>=1;i--) |
76 | //注意题目中要求的搜索优先级，靠西最优先靠南其次。 |
77 | for(int dir=0;dir<4;dir++) |
78 | if((map[i][j]>>dir)%2) |
79 | //若此方向有墙 |
80 | { |
81 | int y=i+(dir-2)%2,x=j+(dir-1)%2; |
82 | if(range(y,x)&&num[i][j]!=num[y][x]) |
83 | //判断是否超界，两个相邻位置的房间编号是否不同。 |
84 | { |
85 | int temp=size[i][j]+size[y][x]; |
86 | //temp表示两房间的面积和。 |
87 | if(max<temp) 若max<temp，则更新max和记录该墙的相关信息。="" {="" max="temp;" wall_y="i;" wall_x="j;" wall="wall_order[dir];" }="" printf("%d\n%d="" %d="" %c\n",max,wall_y,wall_x,wall);="" int="" main()="" freopen("castle.in","r",stdin);="" freopen("castle.out","w",stdout);="" scanf("%d%d",&m,&n);="" 先输入列，再输入行。="" for(int="" i="1;i<=n;i++)" j="1;j<=m;j++)" scanf("%d",&map[i][j]);="" mark[i][j]="false;" size[i][j]="0;" get_size();="" remove_wall();="" <="" pre=""> </temp)></stdio.h></iostream> |
