首页 > 代码库 > 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 }
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。