首页 > 代码库 > hihocoder offer收割编程练习赛8 B
hihocoder offer收割编程练习赛8 B
思路:
模拟,dfs。
注意题目中的trick,输出一块的时候不要把其他块也输出了。
实现:
1 #include <cstring> 2 #include <iostream> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 7 char a[505][505]; 8 int n, m, minx, miny, maxx, maxy; 9 bool vis[505][505], ok[505][505]; 10 int dx[4] = { 0, 1, 0, -1 }; 11 int dy[4] = { 1, 0, -1, 0 }; 12 13 void dfs(int x, int y) 14 { 15 ok[x][y] = vis[x][y] = true; 16 minx = min(x, minx); 17 miny = min(y, miny); 18 maxx = max(x, maxx); 19 maxy = max(y, maxy); 20 for (int i = 0; i < 4; i++) 21 { 22 int nx = x + dx[i]; 23 int ny = y + dy[i]; 24 if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && a[nx][ny] == ‘1‘) 25 { 26 dfs(nx, ny); 27 } 28 } 29 } 30 int main() 31 { 32 cin >> n >> m; 33 for (int i = 0; i < n; i++) 34 { 35 for (int j = 0; j < m; j++) 36 { 37 cin >> a[i][j]; 38 } 39 } 40 for (int j = 0; j < m; j++) 41 { 42 for (int i = 0; i < n; i++) 43 { 44 if (!vis[i][j] && a[i][j] == ‘1‘) 45 { 46 minx = maxx = i, miny = maxy = j; 47 memset(ok, 0, sizeof(ok)); 48 dfs(i, j); 49 cout << maxx - minx + 1 << " " << maxy - miny + 1 << endl; 50 for (int j = minx; j <= maxx; j++) 51 { 52 for (int k = miny; k <= maxy; k++) 53 { 54 cout << ok[j][k]; 55 } 56 cout << endl; 57 } 58 } 59 } 60 } 61 return 0; 62 }
hihocoder offer收割编程练习赛8 B
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。