剑指Offer_12_矩阵中的路径(参考问题:马踏棋盘)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

例如：

a b c e

s f c s

a d e e

矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

参考问题：

马踏棋盘：将马随机放在国际象棋的 8x8 [0～7][0～7]的某个方格中，马按走棋(日字走法)规则进行移动。每个格子只能走一边，走遍棋盘上全部64个方格。求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。

分析：

此题可采用回朔法。首先在格子中任选一个格子作为路径起点，然后在上下左右的位置寻找下一步，寻找到则进入下一步，若上下左右均没有下一步，则返回上一步的位置从上一步寻找新的路径。矩阵还需一个对应的bool表，来记录走过的路径。

Java实现代码如下：

import java.util.*; public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
if(matrix==null || matrix.length==0 || str==null || str.length==0 || matrix.length!=rows*cols || rows<=0 || cols<=0 || rows*cols < str.length) {
return false ;
} boolean[] visited = new boolean[rows*cols] ;
int[] pathLength = {0} ; for(int i=0 ; i<=rows-1 ; i++) {
for(int j=0 ; j<=cols-1 ; j++) {
if(hasPathCore(matrix, rows, cols, str, i, j, visited, pathLength)) { return true ; }
}
} return false ;
} public boolean hasPathCore(char[] matrix, int rows, int cols, char[] str, int row, int col, boolean[] visited, int[] pathLength) {
boolean flag = false ; if(row>=0 && row<rows && col>=0 && col<cols && !visited[row*cols+col] && matrix[row*cols+col]==str[pathLength[0]]) {
pathLength[0]++ ;
visited[row*cols+col] = true ;
if(pathLength[0]==str.length) { return true ; }
flag = hasPathCore(matrix, rows, cols, str, row, col+1, visited, pathLength) ||
hasPathCore(matrix, rows, cols, str, row+1, col, visited, pathLength) ||
hasPathCore(matrix, rows, cols, str, row, col-1, visited, pathLength) ||
hasPathCore(matrix, rows, cols, str, row-1, col, visited, pathLength) ; if(!flag) {
pathLength[0]-- ;
visited[row*cols+col] = false ;
}
} return flag ;
} }

C++实现如下：

boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
int flag[] = new int[matrix.length];
for (int i = ; i < rows; i++) {
for (int j = ; j < cols; j++) {
if (helper(matrix, rows, cols, i, j, str, , flag))
return true;
}
}
return false;
} boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, int[] flag) {
int index = i * cols + j;
if (i < || i >= rows || j < || j >= cols || matrix[index] != str[k] || flag[index] == )
return false;
if(k == str.length - ) return true;
flag[index] = ;
if (helper(matrix, rows, cols, i - , j, str, k + , flag)
|| helper(matrix, rows, cols, i + , j, str, k + , flag)
|| helper(matrix, rows, cols, i, j - , str, k + , flag)
|| helper(matrix, rows, cols, i, j + , str, k + , flag)) {
return true;
}
flag[index] = ;
return false;
}

参考问题分析：

与上问题相似，需要的是一个8x8的数组，起始均为0，第一步走的格子填1，第二步填2....直至64，说明棋盘遍历完成。递归实现如下。

#include<stdio.h>
#include <stdlib.h>
#include<conio.h>
#define N 8
int cnt=; // 记录马的位置
int n=;
int chess[][]={}; //棋盘
int move[][]={
{,-},{,-},
{,},{,},
{-,},{-,},
{-,-},{-,-}
};
void horse(int ,int );
void printhorse(); int main() //主函数
{
chess[][]=;
horse(,);
return ;
}
void horse(int x,int y) //执行过程
{
int i;
int a,b;
for(i=;i<N;i++)
{
a=x+move[i][];
b=y+move[i][];
if(a>=&&a<N&&b>=&&b<N&&!chess[a][b])
{
chess[a][b]=++cnt;
if(cnt<)
{ horse(a,b); } // 递归
else{
printhorse();
// exit(0); }
chess[a][b]=;//修改ab的值归为0
cnt--;
}
}
}
void printhorse() //输出马踏棋盘
{
int i,j;
printf("输出第%d中解法：\n",n++);
for(i=;i<N;i++)
{
for(j=;j<N;j++)
printf("%3d ",chess[i][j]);
printf("\n");
}
}