首页 > 代码库 > 百度之星初赛A hdu6113
百度之星初赛A hdu6113
度度熊的01世界
题意:中文题
思路:在最外面加一圈0,然后判联通块的个数,1的联通块数量只能是1,否则输出-1,0的联通块只能是1或者2,否则输出-1
AC代码:
#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define ll long long #define endl ("\n") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ft first #define sd second #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=1e5+100; const ll mod=1e9+7; int n,m; int G[105][105],vis[2][105][105]; int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; struct Node{ int xx, yy; }; void bfs(int x, int y, int k){ queue<Node> Q; while(!Q.empty()) Q.pop(); Node now,next; now.xx=x, now.yy=y; Q.push(now), vis[k][x][y]=1; while(!Q.empty()){ now=Q.front(); Q.pop(); for(int i=0; i<4; ++i){ next.xx=now.xx+d[i][0]; next.yy=now.yy+d[i][1]; if(next.xx>n+1 || next.xx<0 || next.yy>m+1 || next.yy<0) continue; if(G[next.xx][next.yy]==k && !vis[k][next.xx][next.yy]){ Q.push(next); vis[k][next.xx][next.yy]=1; } } } } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); while(cin>>n>>m){ mem(G,0), mem(vis,0); for(int i=1; i<=n; ++i){ for(int j=1; j<=m; ++j){ char cc; cin>>cc; G[i][j]=cc-‘0‘; } } int c0=0, c1=0; for(int i=0; i<=n+1; ++i){ for(int j=0; j<=m+1; ++j){ if(G[i][j]==0 && !vis[0][i][j]){ bfs(i,j,0); c0++; } else if(G[i][j]==1 && !vis[1][i][j]){ bfs(i,j,1); c1++; } } } if(c1!=1 || c0>=3) cout<<-1<<endl; else if(c0==1) cout<<1<<endl; else cout<<0<<endl; } return 0; }
百度之星初赛A hdu6113
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。