首页 > 试题广场 >

大家来扫雷

[编程题]大家来扫雷

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

小M最近爱上了扫雷游戏，就是在一个n*m的区域中，有地雷，每一个方格上都有一个数字s，表示在这个方格周围有s颗雷，现在给你一张表明地雷的图，并且指定一个位置点开，请输出点开后的数字情况，若点开的地方的数字为0，则向该方格周围扩展，直到遇到数字或者地图边界为止，若点开的地方为地雷,那么直接输出"GG"。

周围指的是上，左上，左，左下，下，右下，右，右上八个方向。

输入描述:

第一行有两个数字n和m(2<=n,m<=1000)，表示地图的大小，第二行有两个整数x和y(1<=x<=n,1<=y<=m)，表示点击第x行y列的方格，接下来的是一个n行m列的一个矩阵，表示地图，其中.表示空地，*表示地雷。

输出描述:

如果点开的地方为地雷直接输出"GG"。否则输出点击指定位置后的地图，"."表示未点开的空地，"*"表示地雷，数字表示在该方格周围的地雷数目。

示例1

输入

3 4
1 1
....
..*.
....

输出

01..
01*.
01..

算法知识视频讲解

Java

牛客196305255号

需要注意的是，输出结果时，最好一次输出，否则很容易超时。
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n=sc.nextInt();
            int m=sc.nextInt();
            int x=sc.nextInt()-1;
            int y=sc.nextInt()-1;
            char[][] arr=new char[n][m];
            for(int i=0;i<n;i++){
                arr[i]=sc.next().toCharArray();
            }
            
            if(arr[x][y]=='*') {
                System.out.println("GG");
            }else {
                List<Point> list=new ArrayList<>();
                arr[x][y]=getBomb(arr,x,y);
                list.add(new Point(x,y));
                while(list.size()>0) {
                    click(arr,list) ;
                }
                StringBuilder sb=new StringBuilder();
                for(int i=0;i<n;i++) {
                    for(int j=0;j<m;j++) {
                        sb.append(arr[i][j]);
                    }
                    sb.append("\n");
                }
                System.out.println(sb.toString());
            }
        }
        sc.close();
    }
    private static void click(char[][] arr,List<Point> list) {
		Point p=list.remove(0);
		int x=p.getX();
		int y=p.getY();
		if(arr[x][y]!='0')
			return;
		for(int i=x-1;i<=x+1;i++) {
			if(i<0||i>=arr.length)
				continue;
			for(int j=y-1;j<=y+1;j++) {
				if(j<0||j>=arr[0].length||(i==x&&j==y))
					continue;
				if(arr[i][j]=='.') {
					arr[i][j]=getBomb(arr,i,j);
					list.add(new Point(i,j));
				}
			}
		}
	}
	private static char getBomb(char[][] arr,int x,int y) {
		int count=0;
		for(int i=x-1;i<=x+1;i++) {
			if(i<0||i>=arr.length)
				continue;
			for(int j=y-1;j<=y+1;j++) {
				if(j<0||j>=arr[0].length)
					continue;
				if(arr[i][j]=='*') {
					count++;
				}
			}
		}
		return Character.forDigit(count, 10);
	}
}
class Point{
	private int x;
	private int y;
	public Point(int x,int y) {
		this.x=x;
		this.y=y;
	}
	public int getX() {
		return x;
	}
	public int getY() {
		return y;
	}
}

编辑于 2021-03-25 21:15:04 回复(2)