百练2815 城堡问题

Posted on | In |

image

样例输入

4

7

11 6 11 6 3 10 6

7 9 6 13 5 15 5

1 10 12 7 13 7 5

13 11 10 8 10 12 13

 样例输出

5

9

1表示西墙，2表示北墙，4表示东墙，8表
示南墙。每个方块用代表其周围墙的数字之
和表示。

dfs递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<cstring>
#define MAX 50
int fang[MAX][MAX];
int color[MAX][MAX];
int colornum=0,maxroom=0,roomArea;
using namespace std;
void dfs(int i,int j){
	if(color[i][j]) return;
	else{
		color[i][j]=colornum;
		roomArea++; 
		if((fang[i][j]&1)==0) dfs(i,j-1);
		if((fang[i][j]&2)==0) dfs(i-1,j);
		if((fang[i][j]&4)==0) dfs(i,j+1);		
		if((fang[i][j]&8)==0) dfs(i+1,j);	
	}
	

	
}

int m,n;
int main(){
	freopen("11-14.txt","r",stdin);
	cin>>m>>n;

	memset(color,0,sizeof(color));
	memset(fang,0,sizeof(fang));	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>fang[i][j];

		}
	} 

	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)
		{
			if(!color[i][j]){
		
			colornum++;
			roomArea=0; 
			dfs(i,j);
			maxroom=max(maxroom,roomArea);
		}
		} 

	}
	cout<<colornum<<endl;
	cout<<maxroom<<endl;
}

栈方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstring>
#include<stack>
#define MAX 50
int fang[MAX][MAX];
int color[MAX][MAX];
int colornum=0,maxroom=0,roomArea;
using namespace std;
struct room{
	int x;
	int y;
	room(int xx,int yy):x(xx),y(yy){
		
	} 
}; 
void dfs(int i,int j){//一条路走到黑 
	stack<room> s;
	s.push(room(i,j));
	while(!s.empty()){
		room r=s.top();
			    int rx=r.x;
		int ry=r.y; 
		if(color[rx][ry])s.pop();//!!! 
			else{

	color[rx][ry]=colornum;
	roomArea++;
    	if((fang[rx][ry]&1)==0) s.push(room(rx,ry-1));//
    	if((fang[rx][ry]&2)==0) s.push(room(rx-1,ry)); 
    	if((fang[rx][ry]&4)==0) s.push(room(rx,ry+1)); 
    	if((fang[rx][ry]&8)==0) s.push(room(rx+1,ry)); 								           	
	                                                                  
	}
	}
	}

int m,n;
int main(){
	freopen("11-14.txt","r",stdin);
	cin>>m>>n;

	memset(color,0,sizeof(color));
	memset(fang,0,sizeof(fang));	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>fang[i][j];

		}
	} 

	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++)
		{
			if(!color[i][j]){
		
			colornum++;
			roomArea=0; 
			dfs(i,j);
			maxroom=max(maxroom,roomArea);
		}
		} 

	}
	cout<<colornum<<endl;
	cout<<maxroom<<endl;
}