ts实现广度遍历算法w1661824810的博客-

TypeScript实现广度遍历算法

在30 * 30的地图里，点击某个图片，从而遍历所有的图片(且不重复)。
广度遍历算法：
访问点击的图片s，依次访问点击图片s的未被访问相邻的其他图片，一次访问他们尚未访问的其他相邻图片，直到访问完所有的图片。

代码实现

测试图片类

enum EnumImageStatus {//定义图片状态枚举 UNDISCOVER,//未被发现 DISCOVER,//发现 VISITED,//访问完毕 } class TestImage extends egret.Sprite { public status: number; private bitmap: egret.Bitmap; private _i: number; private _j: number; public constructor(i: number, j: number) { super(); this._i = i; this._j = j; this.init(); } private init(): void { this.bitmap = new egret.Bitmap(RES.getRes("bg_jpg")); this.bitmap.width = 100; this.bitmap.height = 100; this.addChild(this.bitmap); this.touchEnabled = true; this.status = EnumImageStatus.UNDISCOVER;//图片默认状态未被发现 } public playEff(): void {//播放闪光特效(测试用) this.light(); } /**   * 增加滤镜   */ private light(): void { var colorMatrix = [ 1, 0, 0, 0, 226, 0, 1, 0, 0, 218, 0, 0, 1, 0, 164, 0, 0, 0, 1, 0 ]; var colorFlilter = new egret.ColorMatrixFilter(colorMatrix); this.bitmap.filters = [colorFlilter]; var clearFilter = () => { if (this.bitmap) { this.bitmap.filters = []; } }   egret.Tween.get(this.bitmap).wait(150).call(clearFilter, this); } public get i(): number { return this._i; } public get j(): number { return this._j; } } 

创建图片

this.arr[] = [];//初始化数据 for (let i = 0; i < 30; i++) { this.arr[i] = [];//初始化数组的第i行 for (var j = 0; j < 30; j++) { this.arr[i][j] = new TestImage(i, j);//创建图片 this.arr[i][j].x = j * 100; this.arr[i][j].y = i * 100; this.addChild(this.arr[i][j]);//添加图片 } } 

给某个图片增加点击事件

private touchTapHandler(e: egret.Event): void { this.bfs(e.data);//调用广度遍历算法 } 

广度遍历算法

private bfs(img: TestImage): void { var arr: TestImage[] = [];  img.status = EnumImageStatus.DISCOVER;//更改当前图片状态为发现状态 var timer: number = egret.getTimer();  img.playEff();//播放闪光特效  arr.push(img);//并且存到数组中 var count: number = 1;//遍历数量 while (arr.length) {//数组的长度不为零时 var image: TestImage = arr.shift();//取出数组首元素 for (var i = image.i - 1; i <= image.i + 1; i++) {//遍历首元素的四周 for (var j = image.j - 1; j <= image.j + 1; j++) { if (i == image.i && j == image.j) {//跳过首元素 continue; } var nextNbr: TestImage = this.nextNbr(i, j);//取出相邻的图片 if (nextNbr && nextNbr.status == EnumImageStatus.UNDISCOVER) {//判断是否存在并且没有被发现      nextNbr.status = EnumImageStatus.DISCOVER;//更改相邻的图片状态      nextNbr.playEff();//播放闪光特效      arr.push(nextNbr);//并且存放到数组中      count++;//遍历数量加1 } } }   image.status = EnumImageStatus.VISITED;//至此，图片访问完毕 }  egret.error(egret.getTimer() - timer);//打印算法执行时间  egret.log(count);//打印遍历数量 } 

获取图片相邻的图片

private nextNbr(i, j): TestImage { if (this.exisit(i, j)) { return this.arr[i][j]; } } 

判断图片是否存在

private exisit(i: number, j: number): boolean { return 0 <= i && i < this.arr.length && 0 <= j && j <= this.arr[i].length && this.arr[i][j] != null; }