首页 > 代码库 > hihocoder offer收割编程练习赛12 C 矩形分割
hihocoder offer收割编程练习赛12 C 矩形分割
思路:
模拟,深搜。
实现:
1 #include <iostream> 2 #include <cstdio> 3 #include <string> 4 using namespace std; 5 6 const int dx[4] = { 0, 1, 0, -1 }; 7 const int dy[4] = { -1, 0, 1, 0 }; 8 9 int n, m, cnt = 0; 10 int a[305][305]; 11 bool vis[305][305]; 12 13 void dfs(int x, int y) 14 { 15 vis[x][y] = true; 16 for (int i = 0; i < 4; i++) 17 { 18 int nx = x + dx[i]; 19 int ny = y + dy[i]; 20 if (nx >= 0 && nx < 3 * n && ny >= 0 && ny < 3 * m && !a[nx][ny] && !vis[nx][ny]) 21 { 22 dfs(nx, ny); 23 } 24 } 25 } 26 27 int main() 28 { 29 scanf("%d %d", &n, &m); 30 getchar(); 31 for (int i = 0; i < n; i++) 32 { 33 for (int j = 0; j < m; j++) 34 { 35 char c = getchar(); 36 if (c == ‘/‘) 37 { 38 a[3 * i][3 * j] = 0; 39 a[3 * i][3 * j + 1] = 0; 40 a[3 * i][3 * j + 2] = 1; 41 a[3 * i + 1][3 * j] = 0; 42 a[3 * i + 1][3 * j + 1] = 1; 43 a[3 * i + 1][3 * j + 2] = 0; 44 a[3 * i + 2][3 * j] = 1; 45 a[3 * i + 2][3 * j + 1] = 0; 46 a[3 * i + 2][3 * j + 2] = 0; 47 } 48 else if (c == ‘\\‘) 49 { 50 a[3 * i][3 * j] = 1; 51 a[3 * i][3 * j + 1] = 0; 52 a[3 * i][3 * j + 2] = 0; 53 a[3 * i + 1][3 * j] = 0; 54 a[3 * i + 1][3 * j + 1] = 1; 55 a[3 * i + 1][3 * j + 2] = 0; 56 a[3 * i + 2][3 * j] = 0; 57 a[3 * i + 2][3 * j + 1] = 0; 58 a[3 * i + 2][3 * j + 2] = 1; 59 } 60 } 61 getchar(); 62 } 63 64 for (int i = 0; i < 3 * n; i++) 65 { 66 for (int j = 0; j < 3 * m; j++) 67 { 68 if (!a[i][j] && !vis[i][j]) 69 { 70 dfs(i, j); 71 cnt++; 72 } 73 } 74 } 75 cout << cnt << endl; 76 return 0; 77 }
hihocoder offer收割编程练习赛12 C 矩形分割
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。