題目大意：將一塊圖像上的黑點在兩種表示法之間轉(zhuǎn)換。

題目分析：遞歸下去。。。

注意：輸出時要注意細節(jié)！！！

?

代碼如下：

# include<iostream> # include<cstdio> # include<vector> # include<string> # include<cstring> # include<algorithm> using namespace std;char p[80][80]; int ans; vector<int>v;int get(int r,int c,int w) {int cnt=0;for(int i=r;i<r+w;++i)for(int j=c;j<c+w;++j)if(p[i][j]=='1')++cnt;return cnt; }int getVal(string path) {int l=path.size();int res=0;for(int i=l-1;i>=0;--i)res=res*5+path[i]-'0';return res; }///查看以(r,c)為左上角，邊長為w的子正方形。下同。 void f1(int r,int c,int w,string path) {int k=get(r,c,w);if(k==0)return ;if(k==w*w){++ans;v.push_back(getVal(path));return ;}f1(r,c,w/2,path+'1');f1(r,c+w/2,w/2,path+'2');f1(r+w/2,c,w/2,path+'3');f1(r+w/2,c+w/2,w/2,path+'4'); }void f2(int r,int c,int w,int s) {if(s==0){for(int i=r;i<r+w;++i)for(int j=c;j<c+w;++j)p[i][j]='*';return ;}int mod=s%5;if(mod==1)f2(r,c,w/2,s/5);else if(mod==2)f2(r,c+w/2,w/2,s/5);else if(mod==3)f2(r+w/2,c,w/2,s/5);else if(mod==4)f2(r+w/2,c+w/2,w/2,s/5); }int main() {//freopen("UVA-806 Spatial Structures.txt","r",stdin);int n,cas=0,flag=0;while(scanf("%d",&n)&&n){v.clear();if(flag)printf("\n");flag=1;if(n>0){for(int i=0;i<n;++i)scanf("%s",p[i]);printf("Image %d\n",++cas);ans=0;f1(0,0,n,"");sort(v.begin(),v.end());int l=v.size();for(int i=0;i<l;++i)printf("%d%c",v[i],(i%12==11||i==l-1)?'\n':' ');printf("Total number of black nodes = %d\n",ans);}if(n<0){n=-n;for(int i=0;i<n;++i){for(int j=0;j<n;++j)p[i][j]='.';p[i][n]=0;}int a;while(scanf("%d",&a)&&a!=-1)v.push_back(a);printf("Image %d\n",++cas);int l=v.size();for(int i=0;i<l;++i)f2(0,0,n,v[i]);for(int i=0;i<n;++i)puts(p[i]);}}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/20143605--pcx/p/4858658.html

總結(jié)

以上是生活随笔為你收集整理的UVA-806 Spatial Structures （四分树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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