练习3 - The Castle(高端转化)

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int W=4,H=7;	//H为现实中的第几列 
int a[W][H]={
	{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}
};
char b[W][H][101];

int x=0,y=0;	
int xo=0,yo=0;
//4个方向可以走 
//同时记录两个方位所要判断的障碍(二进制的位数 -> 左->右)
int mov[4][4] = {{1,0,0,2},{-1,0,2,0},{0,1,1,3},{0,-1,3,1}};
int head,tail;
int t=0;	//记录房间数
int s=0; 
int len=0;
char store0[100];
int g[W][H] = {0};
struct line{
	int x=0;
	int y=0;
	int s=1;	//继承大小 
}; 
line c[101]; 
int main()
{
	//①将十进制int->二进制string 
	for(int i=0;i<W;i++){
		for(int j=0;j<H;j++){
			//二进制补位 
			itoa(a[i][j],b[i][j],2);
			len = strlen(b[i][j]);
			strcpy(store0,"");
			while(4-len>0){
				strcat(store0,"0");
				len++;
			}
			strcat(store0,b[i][j]);
			strcpy(b[i][j],store0);
			cout << b[i][j] << " ";
		}
		cout << endl;
	}
	
	//②开始全局搜索
	for(int i=0;i<W;i++){
		for(int j=0;j<H;j++){
			if(!g[i][j]){
				t++;//房间数+1 
				g[i][j]=1;//先占领后发展
				head=0;tail=1;	//while前重置
				//多起点->多设置 
				c[head].x = i;
				c[head].y = j;
				while(head < tail){
					head++;
					for(int h=0;h<4;h++){
					//备份走之前的位置 
					xo = c[head-1].x;
					yo = c[head-1].y;	
					x = xo + mov[h][0];
					y = yo + mov[h][1];
					if(x>=0 && x<W && y>=0 && y<H && !g[x][y] && (b[xo][yo][mov[h][2]] == '0')&& (b[x][y][mov[h][3]] == '0')){
						g[x][y] = 1;	//到达后，先占领，再发展 
						c[tail].x = x;
						c[tail].y = y;
						c[tail].s = c[head-1].s + 1;	//继承空间 
						tail++;
						//在前进后判断目标
					} 
				}
			}  
			s = c[head-1].s > s ? c[head-1].s : s;
		}
	} 
}
	cout << "房间数：" << t;
	cout << "最大房间：" << (s+1);
    return 0;
}
//cout << "输入："

结果：