首页 > 代码库 > HDU 6113 度度熊的01世界
HDU 6113 度度熊的01世界
度度熊的01世界
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1276 Accepted Submission(s): 466
Problem Description
度度熊是一个喜欢计算机的孩子，在计算机的世界中，所有事物实际上都只由0和1组成。
现在给你一个n*m的图像，你需要分辨他究竟是0，还是1，或者两者均不是。
图像0的定义：存在1字符且1字符只能是由一个连通块组成，存在且仅存在一个由0字符组成的连通块完全被1所包围。
图像1的定义：存在1字符且1字符只能是由一个连通块组成，不存在任何0字符组成的连通块被1所完全包围。
连通的含义是，只要连续两个方块有公共边，就看做是连通。
完全包围的意思是，该连通块不与边界相接触。
现在给你一个n*m的图像，你需要分辨他究竟是0，还是1，或者两者均不是。
图像0的定义：存在1字符且1字符只能是由一个连通块组成，存在且仅存在一个由0字符组成的连通块完全被1所包围。
图像1的定义：存在1字符且1字符只能是由一个连通块组成，不存在任何0字符组成的连通块被1所完全包围。
连通的含义是，只要连续两个方块有公共边，就看做是连通。
完全包围的意思是，该连通块不与边界相接触。
Input
本题包含若干组测试数据。
每组测试数据包含：
第一行两个整数n,m表示图像的长与宽。
接下来n行m列将会是只有01组成的字符画。
满足1<=n,m<=100
每组测试数据包含：
第一行两个整数n,m表示图像的长与宽。
接下来n行m列将会是只有01组成的字符画。
满足1<=n,m<=100
Output
如果这个图是1的话，输出1；如果是0的话，输出0，都不是输出-1。
Sample Input
32 32000000000000000000000000000000000000000000011111111000000000000000000000001111111111100000000000000000000011111111111100000000000000000001111111111111100000000000000000011111100011111000000000000000001111100000011110000000000000000011111000000111110000000000000000111110000000111110000000000000011111100000001111100000000000000111111000000001111100000000000001111110000000001111000000000000011111100000000011111000000000000111110000000000111100000000000001111000000000001111000000000000011110000000000011110000000000000111100000000000011100000000000000111100000000000111000000000000001111000000000001110000000000000011110000000000011100000000000001111000000000011110000000000000011110000000000111100000000000000011100000000001111000000000000000111110000011111110000000000000001111100011111111000000000000000011111111111111100000000000000000011111111111111000000000000000001111111111111000000000000000000001111111111100000000000000000000001111111000000000000000000000000011111000000000000000000000000000000000000000000000000032 3200000000000000000000000000000000000000000000000011111100000000000000000000000000111111100000000000000000000000011111111000000000000000000000001111111110000000000000000000000001111111100000000000000000000000011111111000000000000000000000001111111100000000000000000000000011111110000000000000000000000001111111100000000000000000000000011111111100000000000000000000000111111111000000000000000000000001111111100000000000000000000000111111100000000000000000000001111111111000000000000000000001111111111111000000000000000000111111111111110000000000000000001111111111111100000000000000000011111111111110000000000000000000000011111111110000000000000000000000000011111100000000000000000000000001111111000000000000000000000001111111100000000000000000000000001111111100000000000000000000000011111111000000000000000000000000111111111000000000000000000000001111111110000000000000000000000000111111110000000000000000000000000011111111110000000000000000000000111111111100000000000000000000000111111111000000000000000000000000000000000000003 3101101011
Sample Output
01-1
/** @Author: lyuc* @Date: 2017-08-12 14:12:48* @Last Modified by: lyuc* @Last Modified time: 2017-08-13 21:50:49*/#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>#define LL long long#define INF 0x3f3f3f3f#define MAXN 105using namespace std;char mapn[MAXN][MAXN];int n,m;int res1;int res2;int dir[4][2]={1,0,-1,0,0,1,0,-1};bool vis[MAXN][MAXN];bool ok1(int x,int y){ if(x<0||x>=n||y<0||y>=m||vis[x][y]==true||mapn[x][y]==‘0‘) return false; return true;}void dfs1(int x,int y){ vis[x][y]=true; for(int i=0;i<4;i++){ int fx=x+dir[i][0]; int fy=y+dir[i][1]; if(ok1(fx,fy)==false) continue; dfs1(fx,fy); }}bool ok2(int x,int y){ if(x<0||x>n||y<0||y>m||vis[x][y]==true||mapn[x][y]==‘1‘) return false; return true;}void dfs2(int x,int y){ vis[x][y]=true; for(int i=0;i<4;i++){ int fx=x+dir[i][0]; int fy=y+dir[i][1]; if(ok2(fx,fy)==false) continue; dfs2(fx,fy); }}void init(){ res1=0; res2=0; memset(vis,false,sizeof vis);}int main(){ // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(scanf("%d%d",&n,&m)!=EOF){ init(); for(int i=1;i<=n;i++){ scanf("%s",mapn[i]+1); } n++; m++; for(int i=0;i<=n;i++){ mapn[i][0]=‘0‘; mapn[i][m]=‘0‘; } for(int i=0;i<=m;i++){ mapn[0][i]=‘0‘; mapn[n][i]=‘0‘; } //找1联通块 for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ if(mapn[i][j]==‘1‘){ if(vis[i][j]==true) continue; res1++; dfs1(i,j); } } } //找0联通快 memset(vis,false,sizeof vis); for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ if(mapn[i][j]==‘0‘){ if(vis[i][j]==true) continue; res2++; dfs2(i,j); } } } if(res1==1&&res2==1){ puts("1"); }else if(res1==1&&res2==2){ puts("0"); }else{ puts("-1"); } } return 0;}
HDU 6113 度度熊的01世界
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。