华为OD机试真题 新系统 04-19 Java实现【WIFI设备网络规划】

华为OD新系统机试真题 华为OD新系统上机考试真题 4月19号 200分题型WIFI设备网络规划(C/C/Py/Java/Js/Go)题解可点击查看题目描述WIFI网络中专业的网络规划不仅可以提升业务体验还可以减少部署成本。把办公区可以看作一个n* m的网格部分网格包含墙壁(无法放置AP(WI一FI设备)部分为空地(可以放置AP)。每个AP覆盖范围是一个3*3的正方形(包括自身位置、上下左右、以及对角线区域)且AP和AP的覆盖区域不能重叠防止相互干扰。现在给定一个m x n(不超过50 * 50)的网络布局图(墙壁用字符#表示空地用字符.表示)请设计一个算法计算最少放置多少数量的AP来覆盖所有空地?如果不能按条件完成覆盖请返回-1。输入描述第一行输入 m n接下来m行输入每一行字符输出描述最少放置多少数量的AP来覆盖所有空地?如果不能按条件完成覆盖请返回-1。用例1输入3 3 #.# #.# #.#输出1用例2输入4 3 #.# #.# #.# #.#输出2题解思路思路递归回溯预处理每个空地可以看作AP可放置候选集预处理统计每个AP能够覆盖的空地以及覆盖区域利用AP候选集信息统计出每个空地能被覆盖的AP的信息用于后续剪枝。使用pointToAP进行存储递归回溯计算最少AP数创建covered布尔数组跟踪指定编号空地是否被覆盖。创建used[][]布尔数组表示指定位置是否被覆盖用于快速判断AP放置是否会产生冲突。定义ans表示能够覆盖所有空地最少AP数初始可设置为大于等于2500的值即可。接下来就是正常的递归回溯 剪枝进行搜索这道题主要是需要利用以下几个方案进行剪枝提高效率如果当前所用AP数已超过ans直接剪枝。如果当前使用Ap数目 未覆盖空地数 / 9 ans直接剪枝。(未覆盖空地数 / 9) 是理论上最少还需要的AP数本质上这个剪枝就是第一点剪枝的提前剪枝。如果当前放置Ap状态存在某个空地不能在被任意合法AP覆盖直接剪枝优先处理当前可覆盖AP最少的空地作为扩展点利用pointToAP找出符合条件的AP候选位置并优先按照可覆盖空地数多的点进行递归这道题最难度就是上述剪枝明白剪枝逻辑之后接下来就是正常递归回溯逻辑可参照下面代码实现。根据2的逻辑此时如果ans INT_MAX返回-1否则返回ans即可。codeimportjava.util.*;publicclassMain{staticintn,m;staticchar[][]g;staticint[][]idnewint[55][55];staticinttot;// AP结构覆盖点 3x3占用格子staticclassAP{ArrayListIntegerdotsnewArrayList();// 覆盖的.ArrayListint[]cellsnewArrayList();// 3x3占用格子}staticArrayListAPapListnewArrayList();staticArrayListInteger[]pointToAP;// 空地是否被覆盖staticboolean[]coverednewboolean[2500];// 格子是否被占用用于冲突staticboolean[][]usednewboolean[55][55];staticintans;staticint[]dx{-1,-1,-1,0,0,0,1,1,1};staticint[]dy{-1,0,1,-1,0,1,-1,0,1};// 判断是否在网格内staticbooleanin(intx,inty){returnx0xny0ym;}// 预处理候选AP信息staticvoidbuildAP(){for(inti0;in;i){for(intj0;jm;j){if(g[i][j]!.)continue;APapnewAP();for(intk0;k9;k){intxidx[k],yjdy[k];if(!in(x,y))continue;ap.cells.add(newint[]{x,y});// 覆盖空地if(g[x][y].){ap.dots.add(id[x][y]);}}apList.add(ap);}}}// 计算剩余未覆盖点staticintremain(){intc0;for(inti0;itot;i)if(!covered[i])c;returnc;}// 选取最佳点MRV候选最少staticintselectPoint(){intbest-1,bestCnt3000;for(inti0;itot;i){if(covered[i])continue;intcnt0;for(intap:pointToAP[i]){booleanoktrue;// 判断3x3是否冲突for(int[]c:apList.get(ap).cells){if(used[c[0]][c[1]]){okfalse;break;}}if(ok)cnt;}// 无法覆盖直接失败if(cnt0)return-1;if(cntbestCnt){bestCntcnt;besti;}}returnbest;}// DFS回溯staticvoiddfs(intusedCnt){if(usedCntans)return;// 判断是否全部覆盖booleanalltrue;for(inti0;itot;i){if(!covered[i]){allfalse;break;}}if(all){ansusedCnt;return;}// 下界剪枝最多每个AP覆盖9个点intlb(remain()8)/9;if(usedCntlbans)return;// MRV选点intpselectPoint();if(p-1)return;ArrayListIntegercandnewArrayList();// 枚举候选APfor(intap:pointToAP[p]){booleanoktrue;for(int[]c:apList.get(ap).cells){if(used[c[0]][c[1]]){okfalse;break;}}if(ok)cand.add(ap);}// 优先选择覆盖多的APcand.sort((a,b)-apList.get(b).dots.size()-apList.get(a).dots.size());for(intap:cand){ArrayListint[]oldCellsnewArrayList();ArrayListIntegeroldDotsnewArrayList();// 放置AP标记占用for(int[]c:apList.get(ap).cells){if(!used[c[0]][c[1]]){used[c[0]][c[1]]true;oldCells.add(c);}}// 标记覆盖for(intd:apList.get(ap).dots){if(!covered[d]){covered[d]true;oldDots.add(d);}}dfs(usedCnt1);// 回溯恢复for(int[]c:oldCells){used[c[0]][c[1]]false;}for(intd:oldDots){covered[d]false;}}}staticintsolve(){pointToAPnewArrayList[2500];for(inti0;i2500;i)pointToAP[i]newArrayList();tot0;// 空地编号for(inti0;in;i){for(intj0;jm;j){if(g[i][j].){id[i][j]tot;}}}if(tot0)return0;buildAP();// 反向索引点 - APfor(inti0;iapList.size();i){for(intd:apList.get(i).dots){pointToAP[d].add(i);}}ansInteger.MAX_VALUE;dfs(0);returnansInteger.MAX_VALUE?-1:ans;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);nsc.nextInt();msc.nextInt();sc.nextLine();gnewchar[55][55];for(inti0;in;i){g[i]sc.nextLine().toCharArray();}System.out.println(solve());}}