|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2020-5-8 17:36 编辑
题目描述:
- 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。
- [["a","b","c","e"],
- ["s","f","c","s"],
- ["a","d","e","e"]]
- 但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。
-  
- 示例 1:
- 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
- 输出:true
- 示例 2:
- 输入:board = [["a","b"],["c","d"]], word = "abcd"
- 输出:false
- 提示:
- 1 <= board.length <= 200
- 1 <= board[i].length <= 200
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- #include <vector>
- #include <iostream>
- using namespace std;
- void dfs(vector<vector<char> >& input, int i, int j){
- if(i < 0 || i >= input.size() || j < 0 || j >= input[0].size() || input[i][j] == '#' || input[i][j] == 'X') return;
- input[i][j] = '#';
- dfs(input, i - 1, j);
- dfs(input, i + 1, j);
- dfs(input, i, j+1);
- dfs(input, i, j-1);
- }
- void solution(vector<vector<char> >& input){
- if(input.size() == 0) return;
- int row = input.size();
- int col = input[0].size();
- for(int i = 0; i < row; i++){
- for(int j = 0; j < col; j++){
- bool temp = i==0 || j == 0 || i == row-1 || j == col -1;
- if(temp && input[i][j] == 'O'){
- dfs(input, i, j);
- }
- }
- }
-
- for (int i = 0; i < row; i++) {
- for (int j = 0; j < col; j++) {
- if (input[i][j] == 'O') {
- input[i][j] = 'X';
- }
- if (input[i][j] == '#') {
- input[i][j] = 'O';
- }
- }
- }
-
-
-
- }
- int main(void){
- int row;
- vector<vector<char> > input;
- cout << "please send row for the vector:" << endl;
- cin >> row;
- cin.clear();
- cout << "send columns for the vector:" << endl;
- int col;
- cin >> col;
- cin.clear();
- input.resize(row);
- char temp;
- for(int i = 0 ; i < row; i++){
- for(int j = 0; j < col; j++){
- cin >> temp;
- input[i].push_back(temp);
- }
- }
- solution(input);
- for(int i = 0 ; i < row; i++){
- for(int j = 0; j < col; j++){
- cout << input[i][j] << " ";
- }
- cout << endl;
- }
-
- return 0;
- }
复制代码
注意事项:
1.参考链接:https://leetcode-cn.com/problems ... -cha-ji-by-ac_pipe/ |
|