这道题出现在算法课第二次OJ题上，这道题就本身而言，很容易想到用BFS/DFS，有意思的是，在本次OJ上最后一个测试点，由于内存的限制，如果不精心设计数据结构，很容易爆内存
题目描述
Problem description
Given a 2d mm * nn grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.(1≤m≤1000, 1≤n≤1000)
Input
Line 1: m and n.
Line 2: ‘1’ or ‘0’ in grid and split by spaces
Output
Line 1: number of islands.
Sample Input 1
|
1 2 3 4 5 |
4 5 1 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 |
Sample Output 1
|
1 |
1 |
Sample Input 2
|
1 2 3 4 5 |
4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 |
Sample Output 2
|
1 |
3 |
题解
本题可以用DFS/BFS这两种常见的搜索算法进行求解
但是在本次OJ中，由于最后一个测试用例将内存限制的极其严格，而DFS由于需要递归而调用大量的堆栈资源，而导致众多选手败下阵来。但是改成BFS却不曾料到也因为内存问题改了将近一个小时，不断的优化，下面是个人经验总结
- 如果输入的用例只有0/1，或者输入的用例值介于0-255之间，可以将类型定义为bool/char型，减少内存的占用
- 对于常用的一些变量，可以在全局中进行声明，相比在函数中的局部定义而言节省空间
- 搜索算法不一定要设置一个visited数组，比如这题，求连通的区域个数，可将已访问过的元素置0或者置2，来代替visited数组
- 在置0或者置2的时候，紧跟着push入队后进行，也可以节省空间，原因未知
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <stdio.h> #include <stdlib.h> #include <queue> using namespace std; bool island[1000][1000] = { 0 }; int m, n; int temp, temp_n, temp_m; int island_count = 0; int main() { scanf("%d %d", &m, &n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { scanf("%d", &island[i][j]); } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (island[i][j] == 0) { continue; } else { queue< pair<int,int> > q; island[i][j] = 0; //注意置0的位置 q.push({ i,j }); island_count++; while (!q.empty()) { temp_m = q.front().first; temp_n = q.front().second; q.pop(); if (island[temp_m][temp_n + 1] == 1) { q.push({ temp_m , temp_n + 1 }); island[temp_m][temp_n+1] = 0; } if (island[temp_m + 1][temp_n] == 1) { q.push({ temp_m + 1, temp_n }); island[temp_m+1][temp_n] = 0; } if (island[temp_m][temp_n - 1] == 1) { q.push({ temp_m, temp_n - 1 }); island[temp_m][temp_n - 1] = 0; } if (temp_m - 1 >= 0) { if (island[temp_m - 1][temp_n] == 1) { q.push({ temp_m - 1, temp_n }); island[temp_m-1][temp_n ] = 0<strong>; </strong> } } } } } } printf("%d", island_count); system("pause"); return 0; } |
