《剑指offer》--012--矩阵中的路径

r囧r小猫 2022-06-01 08:45 161阅读 0赞

[《剑指offer》–目录索引][offer]

**题目：**

> 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有  
> 字符的路径。路径可以从矩阵中任意一格开始，每一步可以在矩阵中向左、右、  
> 上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入  
> 该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字  
> 母用下划线标出）。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个  
> 字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。  
> A B T G  
> C F C S  
> J D E H

**思路：**

> 这是一个回溯递归的问题，需要注意以下几点：  
> ①可以从任意一格开始：我们使用二维数组的双重for循环把所有坐标的情况都遍历一遍，代表任意位置开始  
> ②走过的格子不能再走：矩阵用字符二维数组表示，我们可以再建一个动态数组，坐标一一对应，记录每个位置是否被走过的状态  
> ③判断一个位置是否是合格的：如果该位置的字符与字符串中字符对应，再判断该位置的上下左右四个位置中是否能继续找到对应字符，能找到代表合格，则继续递归；不能找到，代表不合格，返回结果，并重新寻找该字符

**代码如下：**  
PathInArray.h

PathInArray.c

#ifndef __PATHINARRAY_H__
    #define __PATHINARRAY_H__
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int HasPathCore(const char* arr,int rows,int cols,int row,int col,const char* str,int* PathLength,int* HasVisited);//判断矩阵中是否存在路径
    int HasPath(const char* arr,int rows,int cols,const char* str);//判断矩阵中是否存在路径核心代码
    
    #endif
    [wy@localhost 012 矩阵中的路径]$ cat PathInArray.c
    #include "PathInArray.h"
    
    int HasPath(const char* arr,int rows,int cols,const char* str)//判断矩阵中是否存在路径
    {
        int* HasVisited=(int *)malloc(sizeof(int)*cols*rows);//动态数组，为了对应字符矩阵的每个位置
        memset(HasVisited,0,rows*cols); //全部初始化0，代表每个位置还未被走过
    
        int PathLength=0;//初始化字符串下标为0
        int i=0,j=0;
    
        //可以从矩阵的任意位置开始
        for(;i<rows;i++)
            for(;j<cols;j++)
            {
                if(HasPathCore(arr,rows,cols,i,j,str,&PathLength,HasVisited) == 1)
                {
                    return 1;//1代表有该路径
                }
            }
    
        free(HasVisited);
        HasVisited=NULL;
        return 0;//0代表没有该路径
    }
    
    int HasPathCore(const char* arr,int rows,int cols,int row,int col,const char* str,int* PathLength,int* HasVisited)//判断矩阵中是否存在路径核心代码
    {
        if(str[*PathLength] == '\0')//比较到字符串尾
        {
            return 1;
        }
    
        if(row < 0 || col < 0 || row >= rows || col >= cols)//越界
        {
            return 0;
        }
    
        int hasPath=0;//定义一个变量接收一个位置大上下左右四个位置的返回值，用于判断该位置是否是合格位
        if(arr[row*cols+col] == str[*PathLength] && HasVisited[row*cols+col] == 0)//字符相同并且该位置未被走过
        {
            (*PathLength)++;//字符串的下标加一，往下找
            HasVisited[row*cols+col]=1;//标记该位置已被走过
            hasPath=HasPathCore(arr,rows,cols,row-1,col,str,PathLength,HasVisited)
                  + HasPathCore(arr,rows,cols,row+1,col,str,PathLength,HasVisited)
                  + HasPathCore(arr,rows,cols,row,col-1,str,PathLength,HasVisited)
                  + HasPathCore(arr,rows,cols,row,col+1,str,PathLength,HasVisited);
    
            if(hasPath == 0)//如果该位置的上下左右四个位置在不能找到后续的字符，说明该位置不合该
            {
                (*PathLength)--;//字符串的下标减一，回头再找
                HasVisited[row*cols+col]=0;//取消刚才的标记，为后面有可能再找到该位置做准备
            }
        }   
        else
        {
            return 0;
        }
    
        return hasPath;
    }

test.c

#include "PathInArray.h"
    
    void test()
    {
        const char* arr="ABTGCFCSJDEH";
        const char* str1="BFCE";
        const char* str2="BFCB";
        const char* str3="BFCX";
        printf("%d\n",HasPath(arr,3,4,str1));
        printf("%d\n",HasPath(arr,3,4,str2));
        printf("%d\n",HasPath(arr,3,4,str3));
    }
    
    int main()
    {
        test();
        return 0;
    }

**运行结果：**  
![这里写图片描述][SouthEast]

[offer]: http://blog.csdn.net/w_y_x_y/article/details/79209805
[SouthEast]: /images/20220601/0ecbd33569044401af3ddb9b16baf412.png