【Java每日一题,dfs】矩阵查找字符串

简介: 【Java每日一题,dfs】矩阵查找字符串

Introduction

有一个m*n正整数矩阵(0-9),输入一个字符串,字符串由0-9的数字组成,要求判断是否存在从矩阵中的一点出发,可以从顺序相邻的数字构成该字符串。相同的数字单元只能使用一次


Input

第一行输入两个数字分别是m,n, 1<=m,n<=10


第二行按行输出数字矩阵中的数字,用空格隔开


第三行输入字符串(末尾没有换行)


Output

若可以找到输出”true”,若不能找到输出一个”false”


Sample

input

5 5
3 8 2 4 5 7 5 1 3 0 6 5 8 2 4 8 6 5 2 8 2 5 9 6 4
4318568

output

true

Solution

import java.util.Scanner;
public class Main {
    static int[][] arr;
    static boolean flag=false;
    static String mate;
    static boolean[][] vis;
    static int n,m;
    static int[] X={1,0,-1,0},Y={0,1,0,-1};
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
         n=s.nextInt(); m=s.nextInt();
        arr=new int[n][m];
        vis=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr[i][j]=s.nextInt();
            }
        }
         mate=s.next();
        int begin=mate.charAt(0)-'0';
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dfs(0,i,j);
            }
        }
        System.out.println(flag);
    }
    static void dfs(int len,int x,int y){
        if(len==mate.length()){
            flag=true;
            return;
        }
        if(flag||x<0||x>=n||y<0||y>=m||vis[x][y]||arr[x][y]!=(mate.charAt(len)-'0'))return;
        for(int i=0;i<4;i++){
            vis[x][y]=true;
            dfs(len+1,x+X[i],y+Y[i]);
            vis[x][y]=false;
        }
    }
}

Experience

正常的dfs

相关文章
|
1月前
|
存储 安全 Java
Java零基础-字符串详解
【10月更文挑战第18天】Java零基础教学篇,手把手实践教学!
105 60
|
27天前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
45 6
|
2月前
|
Java 数据库
案例一:去掉数据库某列中的所有英文,利用java正则表达式去做,核心:去掉字符串中的英文
这篇文章介绍了如何使用Java正则表达式从数据库某列中去除所有英文字符。
56 15
|
2月前
|
Java
JAVA易错点详解(数据类型转换、字符串与运算符)
JAVA易错点详解(数据类型转换、字符串与运算符)
51 4
|
3月前
|
Java 数据库
java小工具util系列1:日期和字符串转换工具
java小工具util系列1:日期和字符串转换工具
53 3
|
3月前
|
SQL Java 索引
java小工具util系列2:字符串工具
java小工具util系列2:字符串工具
20 2
|
3月前
|
存储 移动开发 Java
java核心之字符串与编码
java核心之字符串与编码
25 2
|
3月前
|
Java
Java实现:将带时区的时间字符串转换为LocalDateTime对象
通过上述方法,你可以将带时区的时间字符串准确地转换为 `LocalDateTime`对象,这对于处理不需要时区信息的日期和时间场景非常有用。
828 4
|
3月前
|
算法 Oracle Java
Java字符串拼接技术演进及阿里巴巴的贡献
本文主要讲述了Java字符串拼接技术的演进历程,以及阿里巴巴贡献的最新实现 PR 20273。
136 11
|
3月前
|
算法 Oracle Java
Java字符串拼接技术演进及阿里巴巴的贡献
本文主要讲述了Java字符串拼接技术的演进历程,以及阿里巴巴贡献的最新实现 PR 20273。