首页 > 代码库 > 百度之星初赛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