大暴力搜索题。
建图时，我的建图方法是偶数行偶数列为房子，奇数行奇数列是实墙（其实这些点是不再存在的）。
其他先赋值为没有墙，在根据输入来添墙。
看图更直观一点
样例图：
这样用bfs染色，就能做出前两问。
后两问，枚举每一面墙，如果墙两侧的房间不在一个大房间里，就可以合并，这样不断枚举更新答案。
还有难点是
构图。
#include #include #include #include #include using namespace std;int z[20][5],n,m;int a[201][201];int num[201*201],color[201][201],color_num,ansnum;struct H{ int x,y;}; void pre(){ z[1][1]=1;z[2][2]=1;z[3][1]=1,z[3][2]=1;z[4][3]=1;z[5][1]=1,z[5][3]=1; z[6][2]=1,z[6][3]=1;z[7][1]=1,z[7][2]=2,z[7][3]=4;z[8][4]=1;a[9][1]=1; z[9][4]=1;z[10][2]=1,z[10][4]=1;z[11][1]=1,z[11][2]=1,z[11][4]=1; z[12][3]=1;z[12][4]=1;z[13][1]=1,z[13][3]=1,z[13][4]=1;z[14][2]=1; z[14][3]=1,z[14][4]=1;z[15][1]=1,z[15][2]=1,z[15][3]=1,z[15][4]=1;}void build(){ for(int i=1;i<=2*n+1;i++) for(int j=1;j<=2*m+1;j++) a[i][j]=1;//空墙 for(int i=1;i<=2*n+1;i++) for(int j=1;j<=2*m+1;j++) if(i%2&&j%2) a[i][j]=-1;//实墙 for(int i=2;i<=2*n;i+=2) for(int j=2;j<=2*m;j+=2) a[i][j]=0;//房间 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int x;scanf("%d",&x); if(z[x][1]) a[2*i][2*j-1]=-1; if(z[x][2]) a[2*i-1][2*j]=-1; if(z[x][3]) a[2*i][2*j+1]=-1; if(z[x][4]) a[2*i+1][2*j]=-1; }}void bfs(int x,int y){ queue q; H p;p.x=x,p.y=y; q.push(p); while(!q.empty()) { H l;H k=q.front();q.pop(); if(k.x+2<=2*n) if(a[k.x+1][k.y]==1&&!color[k.x+2][k.y]) {color[k.x+2][k.y]=color[k.x][k.y];l.x=k.x+2,l.y=k.y;q.push(l);} if(k.x-2>=2) if(a[k.x-1][k.y]==1&&!color[k.x-2][k.y]) {color[k.x-2][k.y]=color_num;l.x=k.x-2,l.y=k.y;q.push(l);} if(k.y+2<=2*m) if(a[k.x][k.y+1]==1&&!color[k.x][k.y+2]) {color[k.x][k.y+2]=color_num;l.x=k.x,l.y=k.y+2;q.push(l);} if(k.y-2>=2) if(a[k.x][k.y-1]==1&&!color[k.x][k.y-2]) {color[k.x][k.y-2]=color_num;l.x=k.x,l.y=k.y-2;q.push(l);} }}int main(){ pre(); scanf("%d%d",&m,&n); for(int i=2;i<=2*n;i+=2) for(int j=2;j<=2*m;j+=2) if(!color[i][j]) color[i][j]=++color_num,bfs(i,j); for(int i=2;i<=2*n;i+=2) for(int j=2;j<=2*m;j+=2) num[color[i][j]]++; for(int i=1;i<=color_num;i++) ansnum=max(ansnum,num[i]); printf("%d\n%d\n",color_num,ansnum); int maxn=0,X,Y;char dir; for(int j=2*m+1;j>=1;j--)for(int i=1;i<=2*n+1;i++) { if((i%2==0)&&j%2==1&&a[i][j]==-1&&color[i][j-1]!=color[i][j+1])//要东墙 { int p=num[color[i][j-1]]+num[color[i][j+1]]; if(p>=maxn) {maxn=p,dir='E',X=i/2,Y=(j-1)/2;} } if(i%2==1&&(j%2==0)&&a[i][j]==-1&&color[i-1][j]!=color[i+1][j])//要北墙 { int p=num[color[i-1][j]]+num[color[i+1][j]]; if(p>=maxn) {maxn=p,dir='N',X=(i+1)/2,Y=j/2;} } } printf("%d\n%d %d %c",maxn,X,Y,dir); return 0;}