企业官网建设流程全解析

上海 餐饮网站建设 会员系统,北京网站建设 网络推广,哪家网站开发好,wordpress怎么更换系统文件题目链接#xff1a;1970. 你能穿过矩阵的最后一天#xff08;困难#xff09; 算法原理#xff1a; 解法#xff1a;深搜DFS 方法一#xff1a;反向dfs 13ms击败94.50% 时间复杂度O(mn) ①初始时网格全是水#xff0c;从最后一天往回推#xff0c;每天把一个水单元格变…题目链接1970. 你能穿过矩阵的最后一天困难算法原理解法深搜DFS方法一反向dfs13ms击败94.50%时间复杂度O(mn)①初始时网格全是水从最后一天往回推每天把一个水单元格变成陆地②检查新恢复的陆地能否从第一行连接到最后一行(上下左右四个方向检查)首次满足时即代表是正向最后一次能走通的路径其天数即为答案方法二正向dfs5ms击败100.00%时间复杂度O(mn)①初始时网格全是陆地从第一天开始推每天把一个陆地单元格变成水②检查水单元格能否从最左列连接到最右列(八个方向检查)首次满足时即代表是所有路径都被封死的时候其前一天即为答案③细节因为题目的day并非封死之后的天数而是首次封死的触发天而这一天恰好是最后能过河的天所以返回的不是day-1Java代码class Solution { //方法一反向dfs int[] dxnew int[]{0,0,1,-1}; int[] dynew int[]{1,-1,0,0}; int m,n; public int latestDayToCross(int _m, int _n, int[][] cells) { m_m;n_n; //0水1已恢复但未验证连通性的陆地2已恢复且有连通性的陆地 byte[][] statenew byte[m][n]; //从最后一天开始逐步恢复陆地 for(int daycells.length-1;;day--){ //获取第day天被淹没的单元格,正确映射下标 int[] cellcells[day]; int rcell[0]-1; int ccell[1]-1; //将该单元格恢复为陆地待验证连通性 state[r][c]1; //核心判断新恢复的陆地能否连通第一行和最后一行 if(dfsup(r,c,state)dfsdown(r,c,state)) return day; } } //判断能否连通第一行 private boolean dfsup(int r,int c,byte[][] state){ //如果当前单元格本身就在第一行直接返回 if(r0) return true; //遍历四个方向看能否连通上 for(int k0;k4;k){ int xrdx[k],ycdy[k]; //坐标合法邻域能连通上 if(x0xmy0ynstate[x][y]2) return true; } return false; } //判断能否连通最后一行 private boolean dfsdown(int r,int c,byte[][] state){ //本身就在最后一行直接返回 if(rm-1) return true; //标记当前单元格为能连通的单元格 state[r][c]2; //遍历四个方向递归检查连通性 for(int k0;k4;k){ int xrdx[k],ycdy[k]; //保证坐标合法邻域是待验证的陆地 if(x0xmy0ynstate[x][y]1) //如果邻域能连接最后一行则当前单元格也能 if(dfsdown(x,y,state)) return true; } return false; } }class Solution { //方法二正向dfs int[] dxnew int[]{0,0,1,-1,1,1,-1,-1}; int[] dynew int[]{1,-1,0,0,1,-1,1,-1}; int m,n; public int latestDayToCross(int _m, int _n, int[][] cells) { m_m;n_n; //0陆地1未连通的水2已连通的水 byte[][] statenew byte[m][n]; //从第一天开始连通水 for(int day0;;day){ //获取第day天被淹没的单元格,正确映射下标 int[] cellcells[day]; int rcell[0]-1; int ccell[1]-1; //将该单元格用水淹没待验证连通性 state[r][c]1; //核心判断新水能否连接最左列和最右列 if(dfsleft(r,c,state)dfsright(r,c,state)) return day; } } //判断能否连通最左列 private boolean dfsleft(int r,int c,byte[][] state){ //如果当前单元格本身就在最左列直接返回 if(c0) return true; //遍历八个方向看能否连通上 for(int k0;k8;k){ int xrdx[k],ycdy[k]; //坐标合法邻域能连通上 if(x0xmy0ynstate[x][y]2) return true; } return false; } //判断能否连通最右列 private boolean dfsright(int r,int c,byte[][] state){ //本身就在最后一行直接返回 if(cn-1) return true; //标记当前单元格为能连通的单元格 state[r][c]2; //遍历八个方向递归检查连通性 for(int k0;k8;k){ int xrdx[k],ycdy[k]; //保证坐标合法邻域是待验证的水 if(x0xmy0ynstate[x][y]1) //如果邻域能连接最右列则当前单元格也能 if(dfsright(x,y,state)) return true; } return false; } }