用DFS在2D地图上找连通分量的问题
例4 蓝桥杯——全球变暖
题目大意是有一张NxN像素的照片,图片中”#”代表陆地,”.”代表海洋。”上下左右”4连通连成一片的陆地组成一座岛屿。...参数xym表示现在搜索到(x, y)这个像素,并且(x, y)以及后续搜到的与(x, y)连通的像素都属于第m个连通分量
对于(x, y)我们要搜索它的4个邻居像素(x+1, y), (x-1, y...如果(nx, ny)是尚未被标记陆地,就继续从(nx, ny)开始递归搜索下去。...所以样例中一横排4个#和一竖列4个#不算形状相同
我们可以用下面的算法判断两个岛屿是否形状相同。首先我们为每一个陆地像素编号,具体来说i行j列(从0开始计数)的像素(i, j)的编号是i*m+j。...例如上图样例中,(1, 2, 3, 4)与(14, 15, 16, 17)对于编号的差14-1=15-2=16-3=17-4都是13,所以两座岛屿形状相同。