HDU1312 Red and Black（dfs+连通性问题）-白红宇

HDU1312 Red and Black（dfs+连通性问题）

阅读量：3968 次

发布时间：2019-05-24

本文共 1643 字，大约阅读时间需要 5 分钟。

这有一间铺满方形瓷砖的长方形客房。每块瓷砖的颜色是红色或者黑色。一个人站在一块黑色瓷砖上，他可以从这块瓷砖移动到相邻（即，上下左右）的四块瓷砖中的一块。但是他只能移动到黑色瓷砖上，而不能移动到红色瓷砖上。

编写一个程序，通过重复上述动作来计算他可以达到的黑色瓷砖的数量。

Input输入包含多组数据。每组数据包含两个正整数W和H; H表示瓷砖的行数，W表示瓷砖的列数。 W和H不超过20。

瓷砖的颜色用字符表示，如下所示。

'.' - 黑色瓷砖

'#' - 红色瓷砖

'@' - 站在黑色瓷砖上的人（每组数据中只有一个）

Output对于每组数据，你的程序应输出一行，其中包含他可以到达的黑色瓷砖数目。（站着的黑色瓷砖也要包含在内）

Sample Input

6 9....#......#..............................#@...#.#..#.11 9.#..........#.#######..#.#.....#..#.#.###.#..#.#..@#.#..#.#####.#..#.......#..#########............11 6..#..#..#....#..#..#....#..#..###..#..#..#@...#..#..#....#..#..#..7 7..#.#....#.#..###.###...@...###.###..#.#....#.#..0 0

Sample Output

4559613 代码：

import java.util.Scanner;public class Main{        static int n,m,cnt;        static final int N=1005;        static char map[][]=new char[N][N];        static int dx[]={0,0,1,-1};        static int dy[]={1,-1,0,0};        static void dfs(int x,int y){                if(map[x][y]=='.'){                         cnt++;                        map[x][y]='#';                }                for(int i=0;i<4;i++){                        int xx=x+dx[i];                        int yy=y+dy[i];                        if(xx<0 ||yy<0 ||xx>=n ||yy>=m) continue;                        if(map[xx][yy]=='#') continue;                        dfs(xx,yy);                }        }        public static void main(String[] args) {                Scanner scan=new Scanner(System.in);                while(scan.hasNext()){                        m=scan.nextInt();                        n=scan.nextInt();                        if(n==0 && m==0) break;                                                for(int i=0;i

转载地址：http://jbuki.baihongyu.com/

你可能感兴趣的文章