题目描述 分析 代码（已AC）
利用回溯法，从矩阵任一点开始，向四周试探，若满足字符顺序，则走一步并继续试探，直到字符串搜索结束返回true。如果都不满足，则回溯继续搜索。由于不能重复走同一个格子，需要一个额外的布尔数组记录走过的路径，同时，在回溯时要将走过的当前格子标记清除。public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { boolean[] flags = new boolean[matrix.length]; for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(judge(matrix,i,j,rows,cols,str,0,flags)) return true; } } return false; } public boolean judge(char[] matrix,int i, int j, int rows, int cols, char[] str, int idx, boolean[] flags){ int index = i*cols+j; if(i<0 || j<0 || i>=rows || j>=cols || flags[index] || matrix[index]!=str[idx]) return false; if(idx == str.length-1) return true; flags[index] = true; if( judge(matrix, i+1, j, rows, cols, str, idx+1, flags) || judge(matrix, i-1, j, rows, cols, str, idx+1, flags) || judge(matrix, i, j+1, rows, cols, str, idx+1, flags) || judge(matrix, i, j-1, rows, cols, str, idx+1, flags)) return true; flags[index] = false; // 回溯 return false; } }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
