红与黑

[编程题]红与黑

热度指数：3204 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的（上下左右四个方向）黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入描述:

输入包含多组数据。

每组数据第一行是两个整数 m 和 n（1≤m, n≤20）。紧接着 m 行，每行包括 n 个字符。每个字符表示一块瓷砖的颜色，规则如下：

1. “.”：黑色的瓷砖；
2. “#”：白色的瓷砖；
3. “@”：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

输出描述:

对应每组数据，输出总共能够到达多少块黑色的瓷砖。

示例1

输入

9 6
....#.
.....#
......
......
......
......
......
#@...#
.#..#.

输出

算法知识视频讲解

Java

two倩

深度优先遍历

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
int n = scanner.nextInt();
int m = scanner.nextInt();
String[] str = new String[n];
for (int i = 0; i < n; i++) {
str[i] = scanner.next();
}
int x=0;
boolean[][] flag = new boolean[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (str[i].charAt(j) == '@') {//起点位置
System.out.println(dfs(n, m, str, i, j, flag, 0));
x=1;
break;
}
}
if(x==1)
break;
}
}
}

private static int dfs ( int n, int m, String[] str,int i, int j, boolean[][] flag, int count){
if (i < 0 || i >= n || j < 0 || j >= m) {//越界
return 0;
}
if (str[i].charAt(j) == '#') {//如果是白色瓷砖不可以走
return 0;
}
if (flag[i][j]) {//如果已经走过了
return 0;
}
if (str[i].charAt(j) == '.' || str[i].charAt(j) == '@') {//如果是黑色瓷砖
flag[i][j] = true;
//四个路径之和
count = count + 1 + dfs(n, m, str, i - 1, j, flag, count) + dfs(n, m, str, i + 1, j, flag, count) + dfs(n, m, str, i, j - 1, flag, count) + dfs(n, m, str, i, j + 1, flag, count);
}
return count;

}
}

发表于 2022-09-21 15:09:37 回复(0)

Java

reke

// BFS广度优先搜索
import java.util.*;
public class Main{
    static class Node{
        int x, y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String[] str = sc.nextLine().split(" ");
            int m = Integer.parseInt(str[0]);
            int n = Integer.parseInt(str[1]);
            char[][] tiles = new char[m][n];
            // 利用boolean数组来记录走过的路以防重复
            boolean[][] visited = new boolean[m][n];
            // 开始的'@'就算做一个
            int count = 1;
            Node start = null;
            for(int i = 0; i < m; i++){
                String tmp = sc.nextLine();
                for(int j = 0; j < n; j++){
                    tiles[i][j] = tmp.charAt(j);
                    if(tiles[i][j] == '@'){
                        start = new Node(i, j);
                    }
                    // 将'#'也视作走过了
                    if(tiles[i][j] == '#'){
                        visited[i][j] = true;
                    }
                }
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(start);
            visited[start.x][start.y] = true;
            while(!queue.isEmpty()){
                Node cur = queue.poll();
                // 搜索节点cur的四个方向
                for(int i = 0; i < 4; i++){
                    Node next = new Node(cur.x+direction[i][0], cur.y+direction[i][1]);
                    if(next.x >= 0 && next.x < m && next.y >= 0 && next.y < n 
                      && !visited[next.x][next.y]){
                        count++;
                        queue.offer(next);
                        visited[next.x][next.y] = true;
                    }
                }
            }
            System.out.println(count);
        }
    }
}
// DFS深度优先搜索
import java.util.*;
public class Main{
    static int count;
    static int[][] direction = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    public static void dfs(int x, int y, char[][] tiles, int m, int n){
        for(int i = 0; i < 4; i++){
            int xx = x + direction[i][0];
            int yy = y + direction[i][1];
            if(xx >= 0 && xx < m && yy >= 0 && yy < n 
              && tiles[xx][yy] == '.'){
                count++;
                tiles[xx][yy] = '#';
                dfs(xx, yy, tiles, m, n);
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String[] str = sc.nextLine().split(" ");
            int m = Integer.parseInt(str[0]);
            int n = Integer.parseInt(str[1]);
            char[][] tiles = new char[m][n];
            int startx = 0;
            int starty = 0;
            for(int i = 0; i < m; i++){
                String tmp = sc.nextLine();
                for(int j = 0; j < n; j++){
                    tiles[i][j] = tmp.charAt(j);
                    if(tiles[i][j] == '@'){
                        startx = i;
                        starty = j;
                    }
                }
            }
            count = 1;
            dfs(startx, starty, tiles, m, n);
            System.out.println(count);
        }
    }
}

编辑于 2021-07-31 20:51:43 回复(0)

Java

詆調壹點

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int m = sc.nextInt();
			int n = sc.nextInt();
			sc.nextLine();
			Character[][] map = new Character[m][n];
			Node start = null;
			for (int i = 0; i < m; i ++ ) {
				String s = sc.nextLine();
				for (int j = 0; j < n; j ++ ) {
					map[i][j] = s.charAt(j);
					if(s.charAt(j) == '@') start = new Node(i, j);
				}
			}
			int[][] direction = {{0, 1}, {0, - 1}, {1, 0}, { - 1, 0}};
			bfs(map, direction, start);
		}
	}
	public static void bfs(Character[][] map, int[][] direction, Node start) {
		Queue<Node> queue = new LinkedList<Node>();
		boolean[][] visited = new boolean[map.length][map[0].length];
		queue.add(start);
		visited[start.x][start.y] = true;
		int count = 1;
		while ( ! queue.isEmpty()) {
			Node cur = queue.poll();
			for (int i = 0; i < 4; i ++ ) {
				Node next = new Node(cur.x + direction[i][0], cur.y + direction[i][1]);
				if(next.x >= 0 && next.x < map.length && next.y >= 0 && next.y < map[0].length && map[next.x][next.y] != '#' && ! visited[next.x][next.y]) {
					count ++ ;
					queue.add(next);
					visited[next.x][next.y] = true;
				}
			}
		}
		System.out.println(count);
	}
	static class Node {
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

发表于 2016-10-08 18:03:44 回复(0)