//代码虽然长了点，但应该相当清楚吧~~~ //考虑一二问，只需dfs一遍即可求出答案(根据8>4+2+1,4>2+1,2>1，可以判断哪边有墙)
#include<cmath>#include<algorithm> #include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>using namespace std;struct node{ int x,y,zhi;};struct tree{ int PRex,prey;};int t[101][101];//用来记录当前这个位置所在的联通块有多少个房间int a[101][101];//记录题面的数据int b[101][101];//没用int c[101][101];//表示当前位置东边的墙推倒后能构造多大的房间int d[101][101];//表示当前位置北边的墙推倒后能构造多大的房间node e[100010];//记录竖着的墙所在位置以及推倒后构造的房间大小，便于排序node f[100010];//记录横着的墙所在位置以及推倒后构造的房间大小，便于排序int p[101][101];//dfs里的标记数组tree pre[101][101];//记录这个位置是从哪个位置搜索而来int vis[101][101];//可以判断两个位置是否属于同一房间int m,n;int cnt1,cnt2;int cnt;//同一个房间的每个位置的cnt相同int dfs(int x,int y){ vis[x][y]=cnt; p[x][y]=1; int ans=1; if(a[x][y]-8>=0){ a[x][y]-=8; } else{ if(!p[x+1][y]&&x+1<=n){ pre[x+1][y].prex=x; pre[x+1][y].prey=y; ans+=dfs(x+1,y); } } if(a[x][y]-4>=0){ a[x][y]-=4; } else{ if(y+1<=m&&!p[x][y+1]){ pre[x][y+1].prex=x; pre[x][y+1].prey=y; ans+=dfs(x,y+1); } } if(a[x][y]-2>=0){ a[x][y]-=2; } else{ if(x-1>=1&&!p[x-1][y]){ pre[x-1][y].prex=x; pre[x-1][y].prey=y; ans+=dfs(x-1,y); } } if(a[x][y]-1>=0){ a[x][y]-=1; } else{ if(y-1>=1&&!p[x][y-1]){ pre[x][y-1].prex=x; pre[x][y-1].prey=y; ans+=dfs(x,y-1); } } return ans;}bool cmp(node g,node h){ if(g.zhi==h.zhi){ if(g.y==h.y){ return g.x>h.x; } else{ return g.y<h.y; } } return g.zhi>h.zhi;}int main(){ memset(pre,0,sizeof(pre)); int i,j,k; scanf("%d%d",&m,&n); for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ scanf("%d",&a[i][j]); } } int ans=0; int sum=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(!p[i][j]){ ++cnt; int tmp=dfs(i,j); ans=max(tmp,ans); sum++; t[i][j]=tmp; if(vis[i][j]!=vis[i][j+1])//判断推倒后是否可以增加房间面积 c[i][j]+=t[i][j]; if(vis[i][j-1]!=vis[i][j]) c[i][j-1]+=t[i][j]; if(vis[i-1][j]!=vis[i][j]) d[i][j]+=t[i][j]; if(vis[i][j]!=vis[i+1][j]) d[i+1][j]+=t[i][j]; } else{ int u=i,v=j; while(pre[u][v].prex!=0&&pre[u][v].prey!=0){//找到最开始搜的那个点 int tmp=u; u=pre[u][v].prex; v=pre[tmp][v].prey; } t[i][j]=t[u][v]; if(vis[i][j]!=vis[i][j+1]) c[i][j]+=t[i][j]; if(vis[i][j-1]!=vis[i][j]) c[i][j-1]+=t[i][j]; if(vis[i-1][j]!=vis[i][j]) d[i][j]+=t[i][j]; if(vis[i][j]!=vis[i+1][j]) d[i+1][j]+=t[i][j]; } } } int max1=0,max2=0; for(i=0;i<=n+1;i++){ for(j=0;j<=m+1;j++){ e[++cnt1].x=i;e[cnt1].y=j;e[cnt1].zhi=c[i][j]; f[++cnt2].x=i;f[cnt2].y=j;f[cnt2].zhi=d[i][j]; } } sort(e+1,e+cnt1+1,cmp); sort(f+1,f+cnt2+1,cmp); printf("%d/n%d/n",sum,ans); if(e[1].zhi>f[1].zhi){//这里虽然比较冗杂，但按题目意思几个if和else也就好了 printf("%d/n",e[1].zhi); printf("%d %d E/n",e[1].x,e[1].y); } else if(e[1].zhi==f[1].zhi){ if(e[1].x==f[1].x&&e[1].y==f[1].y){ printf("%d/n",f[1].zhi); printf("%d %d N/n",f[1].x,f[1].y); } else{ if(e[1].y<f[1].y){ printf("%d/n",e[1].zhi); printf("%d %d E/n",e[1].x,e[1].y); } else if(e[1].y==f[1].y){ if(e[1].x>f[1].x){ printf("%d/n",e[1].zhi); printf("%d %d E/n",e[1].x,e[1].y); } else{ printf("%d/n",f[1].zhi); printf("%d %d N/n",f[1].x,f[1].y); } } else{ printf("%d/n",f[1].zhi); printf("%d %d N/n",f[1].x,f[1].y); } } } else{ printf("%d/n",f[1].zhi); printf("%d %d N/n",f[1].x,f[1].y); } return 0;}新闻热点
疑难解答
