首页 > 代码库 > CoderForces 327D Block Tower

CoderForces 327D Block Tower

Portal:http://codeforces.com/problemset/problem/327/D

一座红塔200人,一座蓝塔100人,只有与蓝塔相邻才可以建红塔。

‘.‘处可建塔 ‘#‘处不可建塔

可以随便毁塔

在建造能够容纳最多人数的塔集合情况下,输出对塔的操作(SPJ)

 

这是一道水题

这是一道卡输入输出的题

DFS就好,反正就是在联通分量里炸割顶留根

技术分享
 1 #include<iostream> 2 #include<algorithm> 3 #include<set> 4 #include<cstdio> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 #include<vector> 9 using namespace std;10 #define FOR(i,j,k) for(int i=j;i<=k;i++)11 #define FORD(i,j,k) for(int i=j;i>=k;i--)12 #define LL long long13 #define SZ(x) int(x.size())14 #define maxm 51015 #define maxn 51016 string x;17 int dx[]={1,0,-1,0};18 int dy[]={0,1,0,-1};19 int m,n,sum;20 vector<char> al;21 vector<int> ax,ay;22 char ii[maxm][maxn];23 int a[maxm][maxn],vis[maxm][maxn],col[maxm][maxn];24 bool cr(int xx,int yy)25 {26     FOR(i,0,3)27     if(xx+dx[i]>0&&xx+dx[i]<=m&&yy+dy[i]>0&&yy+dy[i]<=n)28     if(col[xx+dx[i]][yy+dy[i]]==1) return true;29     return false;30 }31 void dfs(int x,int y)32 {33     vis[x][y]=1;34     /*if(cr(x,y)) {al.push_back(‘R‘);ax.push_back(x);ay.push_back(y);col[x][y]=2;sum++;}35     else */{al.push_back(B);ax.push_back(x);ay.push_back(y);col[x][y]=1;sum++;}36     FOR(i,0,3)37     if(x+dx[i]>0&&x+dx[i]<=m&&y+dy[i]>0&&y+dy[i]<=n)38     if(a[x+dx[i]][y+dy[i]]) if(!vis[x+dx[i]][y+dy[i]]) dfs(x+dx[i],y+dy[i]);39     if(col[x][y]==1) if(cr(x,y)) { al.push_back(D);ax.push_back(x);ay.push_back(y);40      al.push_back(R);ax.push_back(x);ay.push_back(y);col[x][y]=2;sum+=2;}41 }42 int main()43 {44 cin>>m>>n;45 FOR(i,1,m)46 {scanf("%s",&ii[i][1]);47 FOR(j,1,n)48 {49 a[i][j]=(ii[i][j]==.);50 }51 }52 FOR(i,1,m)53 FOR(j,1,n)54 if(a[i][j]&&!vis[i][j]) dfs(i,j);55 cout<<sum<<endl;56 FOR(i,0,SZ(al)-1)57 printf("%c %d %d\n",al[i],ax[i],ay[i]);58 return 0;59 }
特别丑的原代码(AC)
技术分享
 1 #include<iostream> 2 #include<algorithm> 3 #include<set> 4 #include<cstdio> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 #include<sstream> 9 using namespace std;10 #define FOR(i,j,k) for(int i=j;i<=k;i++)11 #define FORD(i,j,k) for(int i=j;i>=k;i--)12 #define LL long long13 #define SZ(x) int(x.size())14 #define maxm 51015 #define maxn 51016 char x;17 stringstream ans;18 int dx[]={1,0,-1,0};19 int dy[]={0,1,0,-1};20 int m,n,sum;21 char ii[maxm][maxn];22 int a[maxm][maxn],vis[maxm][maxn],col[maxm][maxn];23 bool cr(int xx,int yy)24 {25     FOR(i,0,3)26     if(xx+dx[i]>0&&xx+dx[i]<=m&&yy+dy[i]>0&&yy+dy[i]<=n)27     if(col[xx+dx[i]][yy+dy[i]]==1) return true;28     return false;29 }30 void dfs(int x,int y)31 {32     vis[x][y]=1;33     ans<<"B "<<x<< <<y<<"\n";col[x][y]=1;sum++;34     FOR(i,0,3)35     if(x+dx[i]>0&&x+dx[i]<=m&&y+dy[i]>0&&y+dy[i]<=n)36     if(a[x+dx[i]][y+dy[i]]) if(!vis[x+dx[i]][y+dy[i]]) dfs(x+dx[i],y+dy[i]);37     if(col[x][y]==1) if(cr(x,y)) {     ans<<"D "<<x<< <<y<<"\n";38      ans<<"R "<<x<< <<y<<"\n";col[x][y]=2;sum+=2;}39 }40 int main()41 {42 cin>>m>>n;43 FOR(i,1,m)44 FOR(j,1,n)45 {46     cin>>x;47     a[i][j]=(x==.);48 }49 FOR(i,1,m)50 FOR(j,1,n)51 if(a[i][j]&&!vis[i][j]) dfs(i,j);52 cout<<sum<<endl;53 cout<<ans.str();54 return 0;55 }
改后依然很丑的代码

输出黑科技sstream orz

#include<sstream> x;x<<.....;cout<<x.str();

输入黑科技

scanf("%s",&string[i][1]);

 

技术分享

 

CoderForces 327D Block Tower