找单词华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 200分题型华为OD机试双机位B卷真题目录点击查看: 华为OD机试双机位B卷真题题库目录机考题库 算法考点详解题目描述给一个字符串和一个二维字符数组如果该字符串存在于该数组中则按字符串的字符顺序输出字符串每个字符所在单元格的位置下标字符串如果找不到返回字符串“N”。需要按照字符串的字符组成顺序搜索且搜索到的位置必须是相邻单元格其中“相邻单元格”是指那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。假定在数组中最多只存在一个可能的匹配。输入描述第1行为一个数字N指示二维数组在后续输入所占的行数。第2行到第N1行输入为一个二维大写字符数组每行字符用半角,分割。第N2行为待查找的字符串由大写字符组成。二维数组的大小为N*N0N100。单词长度K0K1000。输出描述出一个位置下标字符串拼接格式为第1个字符行下标”,”第1个字符列下标”,”第2个字符行下标”,”第2个字符列下标… ”,”第N个字符行下标”,”第N个字符列下标。用例1输入4 A,C,C,F C,D,E,D B,E,S,S F,E,C,A ACCESS输出0,0,0,1,0,2,1,2,2,2,2,3说明ACCESS分别对应二维数组的[0,0] [0,1] [0,2] [1,2] [2,2] [2,3]下标位置。题解思路:递归回溯求解正确处理输入数据使用matrix存储输入矩阵target存储待查找字符串这部分比较简单不多加赘诉。二层循环遍历输入矩阵matrix当找到matrix[i][j] targe[0]时从此处尝试使用递归回溯查找完整匹配路径如果当前位置能找出一条合法的匹配路径直接输出这条路径否则尝试枚举其它点。递归回溯的逻辑大致如下限制题目要求同一个单元格内的字母不允许被重复使用,使用visisted数组进行防止重复访问一个单元格。题目要求搜索到的位置必须是相邻单元格其中“相邻单元格”是指那些水平相邻或垂直相邻的单元格限制住下个搜索访问。核心逻辑如果当前matrix[x][y] targe[k]记录visted[x][y] true, 以及对应坐标DFS往四周搜索targe的下一个字符。重复核心逻辑如果有一条路径能够实现最终k target.size()-1说明找到一个合法路径返回true。 如果不能找到一条合法路径返回false。c#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includemap using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vectorstring split(const string str, const string delimiter) { vectorstring result; size_t start 0; size_t end str.find(delimiter); while (end ! string::npos) { result.push_back(str.substr(start, end - start)); start end delimiter.length(); end str.find(delimiter, start); } // 添加最后一个部分 result.push_back(str.substr(start)); return result; } bool dfs(const int n, int x, int y, string target, int k, vectorvectorint path, vectorvectorbool visited, vectorvectorstring matrix) { // 越界 || 重复访问 || 不能匹配 if (x 0 || x n || y 0 || y n || visited[x][y] || matrix[x][y][0] ! target[k]) { return false; } path.push_back({x, y}); visited[x][y] true; // 完整匹配 if (k target.size() - 1) { return true; } // 定义四个方向 vectorvectorint direct {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 往四个方向尝试递归 for (int i 0; i 4; i) { int nx x direct[i][0]; int ny y direct[i][1]; bool res dfs(n, nx, ny, target, k 1, path, visited, matrix); if (res) { return true; } } // 回溯 visited[x][y] false; path.pop_back(); return false; } // 寻找路径 string findPath(vectorvectorstring matrix, string target) { int n matrix.size(); vectorvectorint path; vectorvectorbool visited(n, vectorbool(n, false)); for (int i 0; i n; i) { for (int j 0; j n; j) { if (matrix[i][j][0] target[0]) { bool result dfs(n, i, j, target, 0, path, visited, matrix); // 找到一条可行路径并且题目说明答案唯一,直接构造结果返回 if (result) { string result; for (int k 0; k path.size(); k) { result to_string(path[k][0]) , to_string(path[k][1]) ,; } // 去除末尾的, result.pop_back(); return result; } } } } return N; } int main() { // 接受输入 int n; cin n; vectorvectorstring matrix(n); cin.ignore(); for (int i 0; i n; i) { string line; getline(cin, line); // 按照,进行切割得到字符串数组 matrix[i] split(line, ,); } string target; getline(cin, target); string res findPath(matrix, target); cout res; return 0; }JAVAimport java.util.*; public class Main { static int n; static String target; static String[][] matrix; static boolean[][] visited; static Listint[] path new ArrayList(); // DFS 搜索函数 static boolean dfs(int x, int y, int k) { // 越界 || 已访问 || 当前字符不匹配 if (x 0 || x n || y 0 || y n || visited[x][y] || matrix[x][y].charAt(0) ! target.charAt(k)) { return false; } path.add(new int[]{x, y}); visited[x][y] true; // 匹配到最后一个字符 if (k target.length() - 1) { return true; } // 四个方向 int[][] direct {{0,1},{0,-1},{1,0},{-1,0}}; for (int[] d : direct) { if (dfs(x d[0], y d[1], k 1)) { return true; } } // 回溯 visited[x][y] false; path.remove(path.size() - 1); return false; } static String findPath() { visited new boolean[n][n]; for (int i 0; i n; i) { for (int j 0; j n; j) { if (matrix[i][j].charAt(0) target.charAt(0)) { // 尝试DFS找寻一条合法路径 if (dfs(i, j, 0)) { StringBuilder sb new StringBuilder(); for (int[] p : path) { sb.append(p[0]).append(,).append(p[1]).append(,); } sb.setLength(sb.length() - 1); // 去掉末尾逗号 return sb.toString(); } } } } return N; } public static void main(String[] args) { Scanner sc new Scanner(System.in); n sc.nextInt(); sc.nextLine(); matrix new String[n][]; for (int i 0; i n; i) { String line sc.nextLine(); matrix[i] line.split(,); } target sc.nextLine(); System.out.println(findPath()); } }Pythondefdfs(n,x,y,target,k,path,visited,matrix):# 越界 || 已访问 || 不匹配ifx0orxnory0orynorvisited[x][y]ormatrix[x][y][0]!target[k]:returnFalsepath.append((x,y))visited[x][y]Trueifklen(target)-1:returnTrue# 四个方向fordx,dyin[(0,1),(0,-1),(1,0),(-1,0)]:ifdfs(n,xdx,ydy,target,k1,path,visited,matrix):returnTrue# 回溯visited[x][y]Falsepath.pop()returnFalsedeffindPath(matrix,target):nlen(matrix)visited[[False]*nfor_inrange(n)]path[]foriinrange(n):forjinrange(n):# 尝试从此处DFS进行搜索合法路径ifmatrix[i][j][0]target[0]:ifdfs(n,i,j,target,0,path,visited,matrix):return,.join(f{x},{y}forx,yinpath)returnNif__name____main__:nint(input())matrix[input().split(,)for_inrange(n)]targetinput().strip()print(findPath(matrix,target))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,line{input.push(line);}).on(close,(){letnparseInt(input[0]);// 读取矩阵letmatrix[];for(leti0;in;i){matrix.push(input[i1].split(,));// 按 , 分割}// 读取目标字符串lettargetinput[n1];// visited 用于标记访问letvisitedArray.from({length:n},()Array(n).fill(false));// path 用于存储路径letpath[];// DFS 搜索函数functiondfs(x,y,k){// 越界 || 已访问 || 字符不匹配if(x0||xn||y0||yn||visited[x][y]||matrix[x][y][0]!target[k]){returnfalse;}// 记录路径path.push([x,y]);visited[x][y]true;// 如果匹配到最后一个字符返回成功if(ktarget.length-1)returntrue;// 四个方向继续搜索letdirs[[0,1],[0,-1],[1,0],[-1,0]];for(let[dx,dy]ofdirs){if(dfs(xdx,ydy,k1))returntrue;}// 回溯visited[x][y]false;path.pop();returnfalse;}// 寻找路径functionfindPath(){for(leti0;in;i){for(letj0;jn;j){// 如果首字符匹配尝试从这里开始 DFSif(matrix[i][j][0]target[0]){if(dfs(i,j,0)){// 拼接结果returnpath.map(p${p[0]},${p[1]}).join(,);}}}}returnN;}console.log(findPath());});Gopackagemainimport(bufiofmtosstrings)var(ninttargetstringmatrix[][]stringvisited[][]boolpath[][2]int)// DFS 搜索函数funcdfs(x,y,kint)bool{// 越界 || 已访问 || 字符不匹配ifx0||xn||y0||yn||visited[x][y]||matrix[x][y][0]!target[k]{returnfalse}// 记录路径pathappend(path,[2]int{x,y})visited[x][y]true// 如果匹配到最后一个字符返回成功ifklen(target)-1{returntrue}// 四个方向继续搜索dirs:[][2]int{{0,1},{0,-1},{1,0},{-1,0}}for_,d:rangedirs{ifdfs(xd[0],yd[1],k1){returntrue}}// 回溯visited[x][y]falsepathpath[:len(path)-1]returnfalse}// 寻找路径funcfindPath()string{visitedmake([][]bool,n)fori:rangevisited{visited[i]make([]bool,n)}fori:0;in;i{forj:0;jn;j{// 如果首字符匹配尝试从这里开始 DFSifmatrix[i][j][0]target[0]{ifdfs(i,j,0){// 拼接结果res:for_,p:rangepath{resfmt.Sprintf(%d,%d,,p[0],p[1])}returnres[:len(res)-1]// 去掉最后一个逗号}}}}returnN}funcmain(){reader:bufio.NewReader(os.Stdin)// 读取矩阵大小fmt.Fscanln(reader,n)// 读取矩阵matrixmake([][]string,n)fori:0;in;i{line,_:reader.ReadString(\n)linestrings.TrimSpace(line)matrix[i]strings.Split(line,,)}// 读取目标字符串target,_reader.ReadString(\n)targetstrings.TrimSpace(target)// 输出结果fmt.Println(findPath())}C语言#includestdio.h#includestring.h#defineMAXN105#defineMAXLEN1000// 定义四个方向intdirect[4][2]{{0,1},{0,-1},{1,0},{-1,0}};// DFS 搜索intdfs(constintn,intx,inty,char*target,intk,intpath[][2],int*pathLen,intvisited[][MAXN],charmatrix[][MAXN]){// 越界 || 重复访问 || 不能匹配if(x0||xn||y0||yn||visited[x][y]||matrix[x][y]!target[k]){return0;}path[*pathLen][0]x;path[*pathLen][1]y;(*pathLen);visited[x][y]1;// 完整匹配if(kstrlen(target)-1){return1;}// 往四个方向尝试递归for(inti0;i4;i){intnxxdirect[i][0];intnyydirect[i][1];intresdfs(n,nx,ny,target,k1,path,pathLen,visited,matrix);if(res){return1;}}// 回溯visited[x][y]0;(*pathLen)--;return0;}// 寻找路径voidfindPath(charmatrix[][MAXN],intn,char*target){intpath[MAXLEN][2];intpathLen0;intvisited[MAXN][MAXN];memset(visited,0,sizeof(visited));for(inti0;in;i){for(intj0;jn;j){if(matrix[i][j]target[0]){pathLen0;intresultdfs(n,i,j,target,0,path,pathLen,visited,matrix);// 找到一条可行路径并且题目说明答案唯一,直接构造结果返回if(result){for(intk0;kpathLen;k){printf(%d,%d,path[k][0],path[k][1]);if(k!pathLen-1){printf(,);}}return;}}}}printf(N);}intmain(){// 接受输入intn;scanf(%d,n);getchar();charmatrix[MAXN][MAXN];charline[MAXLEN];for(inti0;in;i){fgets(line,sizeof(line),stdin);// 按照,进行切割得到字符数组intcol0;for(intj0;line[j]!\0;j){if(line[j],||line[j]\n){continue;}matrix[i][col]line[j];}}chartarget[MAXLEN];fgets(target,sizeof(target),stdin);// 去除换行target[strcspn(target,\n)]\0;findPath(matrix,n,target);return0;}