加快政务网站群建设管理,网站制作公司十强,龙岩论坛,wordpress设置导航菜单显示位置题目描述#xff1a; 不是任何人都可以进入桃花岛的#xff0c;黄药师最讨厌像郭靖一样呆头呆脑的人。所以#xff0c;他在桃花岛的唯一入口处修了一条小路#xff0c;这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩#xff0c;我们认为是安全的#xff0c;而有的瓷砖…题目描述 不是任何人都可以进入桃花岛的黄药师最讨厌像郭靖一样呆头呆脑的人。所以他在桃花岛的唯一入口处修了一条小路这条小路全部用正方形瓷砖铺设而成。有的瓷砖可以踩我们认为是安全的而有的瓷砖一踩上去就会有喷出要命的毒气那你就死翘翘了我们认为是不安全的。你只能从一块安全的瓷砖上走到与他相邻的四块瓷砖中的任何一个上但它也必须是安全的才行。 由于你是黄蓉的朋友她事先告诉你哪些砖是安全的、哪些砖是不安全的并且她会指引你飞到第一块砖上第一块砖可能在任意安全位置现在她告诉你进入桃花岛的秘密就是如果你能走过最多的瓷砖并且没有死那么桃花岛的大门就会自动打开了你就可以从当前位置直接飞进大门了。 注意瓷砖可以重复走过但不能重复计数。 输入格式 第一行两个正整数 W 和 H分别表示小路的宽度和长度。 以下 H 行为一个 H×W 的字符矩阵。每一个字符代表一块瓷砖。其中 . 代表安全的砖# 代表不安全的砖代表第一块砖。 输出格式 输出一行只包括一个数即你从第一块砖开始所能安全走过的最多的砖块个数包括第一块砖。 输入输出样例
输入 11 9 .#… .#.#######. .#.#…#. .#.#.###.#. .#.#…#.#. .#.#####.#. .#…#. .#########. … 输出 59 说明/提示 数据规模与约定 对于全部的测试点保证 1≤W,H≤20。 解题思路
利用dfs思想标记走过的路类似于渗透将能走的路都标记住值得注意的是nm是反着输入的。 代码如下可以当dfs模板用
import java.util.Scanner;public class Main {public static int sum 0;public static int n 0;public static int m 0;public static void main(String[] args){Scanner sc new Scanner(System.in);m sc.nextInt();n sc.nextInt();String s1 sc.nextLine();char a[][] new char[n][m];for(int i 0; i n; i ) {String s sc.nextLine();a[i] s.toCharArray();}int indexi 0;int indexj 0;for(int i 0; i n; i )for(int j 0; j m; j )if(a[i][j] ) {indexi i;indexj j;break;}dfs(a, indexi, indexj);System.out.println(sum);}public static void dfs(char a[][], int i, int j) {sum ;int fxx 0;int fyy 0;int fx[] {-1, 1, 0, 0};int fy[] {0, 0, -1, 1};for(int k 0; k 4; k ) {fxx i fx[k];fyy j fy[k];if(fxx 0 fxx n fyy 0 fyy m a[fxx][fyy] .) { a[fxx][fyy] 1;dfs(a, fxx, fyy);}} }
}
