剑指offer--在矩阵中找路径

题目描述
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 例如[a b c e s f c s a d e e]是3*4矩阵,其包含字符串"bcced"的路径,但是矩阵中不包含“abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

典型的回溯题, 代码可当作模版

//
//  s_66.cpp
//  swordOffer
//
//  Created by YangKi on 2017/3/14.
//  Copyright © 2017年 yangqi916. All rights reserved.
//

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

class Solution {
    
    bool findCore(char* matrix, int rows, int cols, char* str, int curRow, int curCol, int& pathLength, vector<vector<bool>>& visited) {
        if(str[pathLength] == '\0')
            return true;
        
        bool hasPath = false;
        
        if(curRow >= 0 && curRow < rows
           && curCol >= 0 && curCol < cols
           && str[pathLength] == matrix[curRow*cols + curCol]
           && visited[curRow][curCol] == false)
        {
            visited[curRow][curCol] = true;
            pathLength++;
            
            if (findCore(matrix, rows, cols, str, curRow + 1, curCol, pathLength, visited)
                || findCore(matrix, rows, cols, str, curRow - 1, curCol, pathLength, visited)
                || findCore(matrix, rows, cols, str, curRow, curCol + 1, pathLength, visited)
                || findCore(matrix, rows, cols, str, curRow, curCol - 1, pathLength, visited))
            {
                hasPath = true;
            }
            
            visited[curRow][curCol] = false;
            pathLength--;
        }
        
        return hasPath;
    }
    
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(matrix == NULL || rows < 1 || cols < 1 || str == NULL)
            return false;
        
        vector<vector<bool>>visited(rows, vector<bool>(cols, false));
        
        int pathLength = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (findCore(matrix, rows, cols, str, i, j, pathLength, visited))
                    return true;
            }
        }
        
        return false;
    }
    
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 《裕语言》速成开发手册3.0 官方用户交流:iApp开发交流(1) 239547050iApp开发交流(2) 10...
    叶染柒丶阅读 27,839评论 5 19
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 134,958评论 19 139
  • 说明: 本文中出现的所有算法题皆来自牛客网-剑指Offer在线编程题,在此只是作为转载和记录,用于本人学习使用,不...
    秋意思寒阅读 1,170评论 1 1
  • 剑指 offer 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成...
    faremax阅读 2,241评论 0 7
  • 剑指offer 最近在牛客网上刷剑指offer的题目,现将题目和答案(均测试通过)总结如下: 第一个只出现一次的字...
    闫阿佳阅读 597评论 0 3