//代碼雖然長了點，但應該相當清楚吧~~~ //考慮一二問，只需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;}新聞熱點
疑難解答
