深搜1--城堡问题
一、心得
这个题目的栈实现可以看一看
也是很基础的迷宫问题，也就是一个深搜
二、题目及分析
三、代码及结果
递归
1 #include2 #include 3 #include 4 using namespace std; 5 int R,C; //行列数 6 int rooms[60][60]; 7 int color[60][60]; //房间是否染色过的标记 8 int maxRoomArea = 0, roomNum = 0; 9 int roomArea;10 void Dfs(int i,int k) {11 if( color[i][k] ) return;12 ++roomArea;13 color[i][k] = roomNum;14 if( (rooms[i][k] & 1) == 0 ) Dfs(i,k-1); //向西走15 if( (rooms[i][k] & 2) == 0 ) Dfs(i-1,k); //向北16 if( (rooms[i][k] & 4) == 0 ) Dfs(i,k+1); //向东17 if( (rooms[i][k] & 8) == 0 ) Dfs(i+1,k); //向南18 } 19 20 int main() {21 freopen("in.txt","r",stdin); 22 cin >> R >> C;23 for( int i = 1;i <= R;++i)24 for ( int k = 1;k <= C; ++k)25 cin >> rooms[i][k];26 memset(color,0,sizeof(color));27 for( int i = 1;i <= R; ++i)28 for( int k = 1; k <= C; ++ k) {29 if( !color[i][k] ) {30 ++ roomNum ; roomArea = 0;31 Dfs(i,k);32 maxRoomArea =max(roomArea,maxRoomArea);33 }34 }35 cout << roomNum << endl;36 cout << maxRoomArea << endl;37 }
栈实现
1 #include2 #include 3 #include 4 using namespace std; 5 int R,C; //行列数 6 int rooms[60][60]; 7 int color[60][60]; //房间是否染色过的标记 8 int maxRoomArea = 0, roomNum = 0; 9 int roomArea;10 struct Room { int r,c; Room(int rr,int cc):r(rr),c(cc) { } };//构造函数用来初始化，11 void Dfs(int r,int c) { //不用递归，用栈解决，程序其他部分不变12 stack stk;13 stk.push(Room(r,c));14 while ( !stk.empty() ) {15 Room rm = stk.top();16 int i = rm.r; int k = rm.c;17 if( color[i][k]) stk.pop();18 else {19 ++ roomArea;20 color [i][k] = roomNum;21 if((rooms[i][k]&1)==0) stk.push(Room(i,k-1));//西22 if((rooms[i][k]&2)==0) stk.push(Room(i-1,k));//北23 if((rooms[i][k]&4) == 0) stk.push(Room(i,k+1));//东24 if((rooms[i][k]&8) == 0) stk.push(Room(i+1,k)); //南25 }26 }27 }28 29 int main() {30 freopen("in.txt","r",stdin); 31 cin >> R >> C;32 for( int i = 1;i <= R;++i)33 for ( int k = 1;k <= C; ++k)34 cin >> rooms[i][k];35 memset(color,0,sizeof(color));36 for( int i = 1;i <= R; ++i)37 for( int k = 1; k <= C; ++ k) {38 if( !color[i][k] ) {39 ++ roomNum ; roomArea = 0;40 Dfs(i,k);41 maxRoomArea =max(roomArea,maxRoomArea);42 }43 }44 cout << roomNum << endl;45 cout << maxRoomArea << endl;46 }
