2017-8-3

題目描述

知道城堡有多少個(gè)房間，每個(gè)房間有多大 把一面單獨(dú)的墻（指兩個(gè)單位間的墻）拆掉以形成一個(gè)更大的房間

解答

代碼寫(xiě)的好長(zhǎng)...

代碼

/* ID: 18795871 PROG: castle LANG: C++ */ #include<iostream> #include<cstring> #include<fstream> using namespace std; const int N = 50;ifstream fin("castle.in"); ofstream fout("castle.out");struct{bool d,x,n,b;int x1,x2,y1,y2,a; }s[N+2][N+2];int r,c; int m,cnt,sum; bool f[N+1][N+1];void init(){ //根據(jù)所給條件判斷哪里有墻 int t;fin>>c>>r;for (int i=1;i<=r;i++){for (int j=1;j<=c;j++){fin>>t;switch(t){ //零的時(shí)候全為默認(rèn)值 case(1):s[i][j].x=true;break;case(2):s[i][j].b=true;break;case(4):s[i][j].d=true;break;case(8):s[i][j].n=true;break;case(3):s[i][j].x=true;s[i][j].b=true;break;case(5):s[i][j].x=true;s[i][j].d=true;break;case(6):s[i][j].b=true;s[i][j].d=true;break;case(9):s[i][j].x=true;s[i][j].n=true;break;case(10):s[i][j].b=true;s[i][j].n=true;break;case(12):s[i][j].d=true;s[i][j].n=true;break;case(7):s[i][j].x=true;s[i][j].b=true;s[i][j].d=true;break;case(11):s[i][j].x=true;s[i][j].b=true;s[i][j].n=true;break;case(13):s[i][j].x=true;s[i][j].d=true;s[i][j].n=true;break;case(14):s[i][j].b=true;s[i][j].d=true;s[i][j].n=true;break;case(15):s[i][j].b=true;s[i][j].d=true;s[i][j].x=true;s[i][j].n=true;}}} }bool con(int i,int j){ //是否越界 if (i>r||j>c||i<1||j<1) return false;return true; }void dfs(int i,int j){ //深搜求出連通的房間數(shù)以及每個(gè)房間相應(yīng)格數(shù) if (!s[i][j].b&&con(i-1,j)&&!f[i-1][j]){f[i-1][j]=true;cnt++;dfs(i-1,j);}if (!s[i][j].n&&con(i+1,j)&&!f[i+1][j]){f[i+1][j]=true;cnt++;dfs(i+1,j);}if (!s[i][j].d&&con(i,j+1)&&!f[i][j+1]){f[i][j+1]=true;cnt++;dfs(i,j+1);}if (!s[i][j].x&&con(i,j-1)&&!f[i][j-1]){f[i][j-1]=true;cnt++;dfs(i,j-1);} }void cal(){ //a用來(lái)確定是否在同一房間內(nèi) for (int i=1;i<=r;i++){for (int j=1;j<=c;j++){if (f[i][j]){if (!s[i][j].x1&&!s[i][j].x2&&!s[i][j].y1&&!s[i][j].y2){s[i][j].a=sum;}if (s[i][j].d&&!s[i][j].x1){s[i][j].x1=cnt; //東面對(duì)應(yīng)房間的格子數(shù)}if (s[i][j].x&&!s[i][j].x2){s[i][j].x2=cnt; //西面對(duì)應(yīng)房間的格子數(shù)}if (s[i][j].n&&!s[i][j].y2){s[i][j].y2=cnt; //南面對(duì)應(yīng)房間的格子數(shù)}if (s[i][j].b&&!s[i][j].y1){s[i][j].y1=cnt; //北面對(duì)應(yīng)房間的格子數(shù)}}}} }void res(){ //求出結(jié)果 int p,q,m=0;char ch;for (int j=1;j<=c;j++){for (int i=r;i>0;i--){if (s[i][j].b){if (s[i][j].a!=s[i-1][j].a&&s[i][j].y1+s[i-1][j].y2>m){m=s[i][j].y1+s[i-1][j].y2;p=i;q=j;ch='N';}}if (s[i][j].d){if (s[i][j].a!=s[i][j+1].a&&s[i][j].x1+s[i][j+1].x2>m){m=s[i][j].x1+s[i][j+1].x2;p=i;q=j;ch='E';}}}}fout<<m<<endl<<p<<" "<<q<<" "<<ch<<endl; }int main() {init();m=0;sum=0;memset(f,false,sizeof(f));for (int i=1;i<=r;i++){for (int j=1;j<=c;j++){if (!f[i][j]){f[i][j]=true;cnt=1;dfs(i,j);m=max(m,cnt);sum++;cal(); }}}fout<<sum<<endl;fout<<m<<endl;res();return 0; }

突然不是很懂以前的想法，說(shuō)一下現(xiàn)在的吧！
1.房間數(shù)直接dfs即可，每一次從沒(méi)有到過(guò)的格子開(kāi)始遍歷，遍歷的次數(shù)就是所有的房間數(shù)，每次統(tǒng)計(jì)當(dāng)前房間格子的總數(shù)就能求出最大值了。
2.比較難的應(yīng)該就是選擇墻來(lái)推翻了，首先我們得明確一下題意，優(yōu)先選擇東邊的墻推翻，若有多個(gè)解，則選擇北邊的墻推翻。嗯，由于我們要計(jì)算房間數(shù)目，假設(shè)第cnt個(gè)房間就表示當(dāng)前的房間號(hào)為cnt，每次的值加一，那么我們就可以用這個(gè)數(shù)來(lái)標(biāo)記每一個(gè)格子屬于哪一個(gè)房間號(hào)，在遍歷房間cnt時(shí)所路過(guò)的格子都是屬于這個(gè)房間的，我們?cè)俦４嬉幌旅總€(gè)房間包含的格子數(shù)，那么我們可以通過(guò)當(dāng)前的格子得到房間號(hào)，通過(guò)房間號(hào)得到當(dāng)前格子所在房間的總的格子數(shù)，這樣我們就得到了我們預(yù)處理的數(shù)據(jù)了。
3.接下來(lái)我們就要選擇墻了，某個(gè)墻的相鄰兩個(gè)房間的格子數(shù)相加就是推翻這個(gè)墻所獲得的格子數(shù)的總和，根據(jù)題意可得，我們應(yīng)該從左到右，從下往上求得我們需要的結(jié)果。

/* ID: 18795871 PROG: castle LANG: C++ */ #include<iostream> #include<fstream> #include<cstring> using namespace std;ifstream fin("castle.in"); ofstream fout("castle.out");const int N = 50; int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0},d[4]={1,2,4,8}; int x[N+1][N+1],cal[N+1][N+1],p[N*N+1]; bool f[N+1][N+1]; int m,n,num,cnt;bool isvalid(int i,int j){if (i<1||j<1||i>n||j>m) return false;return true; }void dfs(int i,int j){for (int k=0;k<4;k++){if (x[i][j]&d[k]) continue;int ii=i+dx[k],jj=j+dy[k];if (!isvalid(ii,jj)||f[ii][jj]) continue;f[ii][jj]=true;cal[ii][jj]=cnt;num++;dfs(ii,jj);} }int main(){int i,j,ma;while (fin>>m>>n){memset(f,false,sizeof(f));cnt=0;ma=0;for (i=1;i<=n;i++){for (j=1;j<=m;j++){fin>>x[i][j];}}for (i=1;i<=n;i++){for (j=1;j<=m;j++){if (!f[i][j]){cnt++;cal[i][j]=cnt;f[i][j]=true;num=1;dfs(i,j);p[cnt]=num;ma=max(num,ma);}}}int res=0,xx,yy;char c;for (j=1;j<=m;j++){for (i=n;i>=1;i--){if (cal[i][j-1]!=cal[i][j]){if (p[cal[i][j-1]]+p[cal[i][j]]>res){res=p[cal[i][j-1]]+p[cal[i][j]];xx=i;yy=j-1;c='E';} } if (cal[i][j]==cal[i-1][j]) continue;if (p[cal[i][j]]+p[cal[i-1][j]]>res){res=p[cal[i][j]]+p[cal[i-1][j]];xx=i;yy=j;c='N';}}}fout<<cnt<<endl<<ma<<endl<<res<<endl<<xx<<" "<<yy<<" "<<c<<endl;}return 0; }

還有一個(gè)需要注意的地方，我們可以根據(jù)當(dāng)前的x[i][j]值直接得到它的周?chē)袥](méi)有墻，dx，dy，與d都是一一對(duì)應(yīng)的，由k得到當(dāng)前要去往哪個(gè)方向，x[i][j]與d[k]相與就能得到k方向有沒(méi)有墻了。

總結(jié)

以上是生活随笔為你收集整理的USACO-Section2.1 The Castle （深度优先搜索）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。