一道canvas算法题（看过记录下）

我觉得蛮有意思的就记录下

题目：平面上有若干个不特定的形状，如下图所示。请写程序求出物体的个数，以及每个不同物体的面积。

解析：要知道有多少个图形，想到的就是先获取图片中的每一个像素点然后判获取像素点的背景颜色（RGBA）。想要获得图片中的每一个像素点，那就可以联想到使用h5的canvas

(function(){let ctxt = canvas.getContext('2d');let img = new Image;let coordinates = [];let h = 200,w = 350;for(let i=0; i<200; i++){coordinates[i] = [];}img.src = './image.png'; //图片路径img.onload = function(){ctxt.drawImage(img, 0, 0);let data = ctxt.getImageData(0, 0, 350, 200).data;//读取整张图片的像素。let x=0,y=0;for(let i =0,len = data.length; i<len;i+=4){let red = data[i],//红色色深green = data[i+1],//绿色色深blue = data[i+2],//蓝色色深alpha = data[i+3];//透明度//把每个像素点，以二位数组的形式展开if(`${red} ${green} ${blue}` === '210 227 199'){coordinates[y][x] = 0;}else{coordinates[y][x] = 1;}x++;if(x >= 350){x = 0;y++;}}console.log(coordinates);}})();

得到类型二维数组（至于为什么是二维数组是因为imageData的data是有width跟height） 

比如：对于宽度为 350，高度为 200 的图片，ImageData.data 的长度应该是 280,000，因为每个像素占用 4 个字节（RGBA）

[R1, G1, B1, A1, R2, G2, B2, A2, R3, G3, B3, A3, ...]

const grid: number[][] = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],[0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0],[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
];

那现在就简单多了 你只需要得到这个二维数组里面的相邻的1就可以了 
最后的算法

// 使用 BFS 实现
function countClustersBFS(grid: number[][]): number {const rows = grid.length;const cols = grid[0].length;let clusterCount = 0;const directions = [[-1, 0], [1, 0], [0, -1], [0, 1],[-1, -1], [-1, 1], [1, -1], [1, 1],];function bfs(x: number, y: number): void {const queue: [number, number][] = [[x, y]];grid[x][y] = 0;while (queue.length > 0) {const [cx, cy] = queue.shift()!;for (const [dx, dy] of directions) {const nx = cx + dx;const ny = cy + dy;if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] === 1) {grid[nx][ny] = 0;queue.push([nx, ny]);}}}}for (let i = 0; i < rows; i++) {for (let j = 0; j < cols; j++) {if (grid[i][j] === 1) {clusterCount++;bfs(i, j);}}}return clusterCount;
}countClustersBFS([
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
])
结果是2