超过扫雷计划的时间限制

问题描述 投票：0回答：1

**作业：**

扫雷是一款 20 世纪 60 年代的视频游戏，在 m×n 的单元格上玩。目标是利用邻近单元格中地雷数量的线索来推断哪些单元格包含隐藏的地雷。编写一个程序 Minesweeper.java，它接受三个整数命令行参数 m、n 和 k，并打印包含 k 个地雷的 m×n 单元网格，使用星号表示地雷，使用整数表示相邻地雷计数（使用两个空格）每个单元格之间的字符）。为此，

**所需的输出：**

在此输入图片描述

**问题：**

当我将 k 数字靠近 

m * n
时，将不会打印所需的输出（生成不同的索引需要很长时间，请查看下面的代码以了解我的意思） 在此输入图像描述。

这是完整的代码：

public class f {
    public static void main(String[] args) {
        int m = Integer.parseInt(args[0]); // column
        int n = Integer.parseInt(args[1]); // row
        int k = Integer.parseInt(args[2]);
        // true when it's a minesweeper otherwise false
        boolean[][] isT = new boolean[m + 2][n + 2];
        boolean[][] isTRand = new boolean[m + 2][n + 2];
        int countofMinesSweeper = 0;
        int[][] v = new int[m + 2][n + 2];
        // mine part :
        if (k == (m * n)) {
            for (int h = 1; h <= m; h++) {
                for (int y = 1; y <= n; y++) {
                    isT[h][y] = true;
                    countofMinesSweeper++;
                }
            }
        }
        while (countofMinesSweeper < k) {
            int mrand = (int) ((Math.random() * (m - 1))) + 1; // 1 => m
            int nrand = (int) ((Math.random() * (n - 1))) + 1; // 1 => n
            if (!isT[mrand][nrand]) {
                countofMinesSweeper++;
                isT[mrand][nrand] = true;
            }
            System.out.println(mrand);
            System.out.println(nrand);
        }
        // printing part and the cases :
        for (int c = 1; c <= m; c++) {
            for (int r = 1; r <= n; r++) {
                if (!isT[c][r]) {
                    if (isT[c][r + 1]) v[c][r]++;
                    if (isT[c][r - 1]) v[c][r]++;
                    if (isT[c + 1][r]) v[c][r]++;
                    if (isT[c - 1][r]) v[c][r]++;
                    if (isT[c - 1][r + 1]) v[c][r]++;
                    if (isT[c - 1][r - 1]) v[c][r]++;
                    if (isT[c + 1][r + 1]) v[c][r]++;
                    if (isT[c + 1][r - 1]) v[c][r]++;
                }
                if (isT[c][r]) {
                    System.out.print(" * ");
                }
                else {
                    System.out.print(" " + v[c][r] + " ");
                }
            }
            System.out.println();
        }
    }
}

注意：我认为问题的原因是两个随机数，我试图找出另一个不使用随机数的解决方案，但我失败了。

java time minesweeper
1个回答
0
投票

您的代码块

while (countofMinesSweeper < k) {
    int mrand = (int) ((Math.random() * (m - 1))) + 1; // 1 => m
    int nrand = (int) ((Math.random() * (n - 1))) + 1; // 1 => n
    if (!isT[mrand][nrand]) {
        countofMinesSweeper++;
        isT[mrand][nrand] = true;
    }
    
    // System.out.println(mrand);
    // System.out.println(nrand);
    
    System.out.println(mrand+"\t"+ nrand);
}

我更改了此处的代码以找到一些更好的东西。

System.out.println(mrand+"\t"+ nrand);

应用输入参数：

8 4 31

你的代码永远不会结束。

因为您的代码中有错误：

7   1
2   3
2   1
6   3
1   2
5   3
7   3
7   1
2   3
7   3
2   2
1   2
6   3
2   1
6   2
1   3
2   2
3   3
2   3
7   2
5   1

输入 

m=8
, 
n=4
, 
k=31

  • 但是你的第一个数字（m）总是 1~7 ，不包括 8。
  • 你的第二个数字（n）总是1~3，不包括4。

你的代码总是填充 7 * 3 = 21，但是当你输入 

k=31
时，它永远不会达到 31。

您可以测试您的输入。

  • 输入 

    8 4 21
    ( 21 = 7 x 3) ，你的代码将会运行得非常快。

  • 输入

    8 4 22
    ( 22 = 21+1, 21 = 7 x 3) ，永远不会结束。 （你的代码总是随机得到（1~7），（1~3），永远不会得到行列8,4）

这就是根本原因。

你的数组从 1 开始，而不是从 0 开始。

但是当你设置列或行时，长度是

-1

然后正确的范围：

m（1~8），n（1~4）。

但是你的代码范围：

m(1~7),n(1~3)

当 K <= your code range (73) 时，工作正常。 但是当 K > 你的代码范围 (73) 时，那么 while 循环永远不会结束。

扫雷器.java

我的代码不重要。

import java.util.ArrayList;

public class MinesSweeper {
    public static void main(String[] args) {

        int m = Integer.parseInt(args[0]); // column
        int n = Integer.parseInt(args[1]); // row
        int k = Integer.parseInt(args[2]);
        // true when it's a minesweeper otherwise false
        boolean[][] isT = new boolean[m + 2][n + 2];
        boolean[][] isTRand = new boolean[m + 2][n + 2];
        int countofMinesSweeper = 0;
        int[][] v = new int[m + 2][n + 2];
        // mine part :
        if (k == (m * n)) {
            for (int h = 1; h <= m; h++) {
                for (int y = 1; y <= n; y++) {
                    isT[h][y] = true;
                    countofMinesSweeper++;
                }
            }
        }
/*
        long startTime = System.currentTimeMillis();  // get start time ms

        while (countofMinesSweeper < k) {
            int mrand = (int) ((Math.random() * (m - 1))) + 1; // 1 => m
            int nrand = (int) ((Math.random() * (n - 1))) + 1; // 1 => n
            if (!isT[mrand][nrand]) {
                countofMinesSweeper++;
                isT[mrand][nrand] = true;
            }
            System.out.println(mrand+"\t"+nrand);
        }

        long endTime = System.currentTimeMillis();    // get end time ms
        long executionTime = endTime - startTime;     // cala execute time
        System.out.println("execute time: " + executionTime + " ms");
*/

        //************************

        long startTime = System.currentTimeMillis();  // get start time ms

        int selectedNum = k;
        ArrayList<Integer> luckyCan=new ArrayList<Integer>();
        for (int i= 1;i<= (m * n) ;i++){
            luckyCan.add(Integer.valueOf(i));
        }
        while (selectedNum > 0) {
            int randomNumber = (int) (Math.random() * luckyCan.size()) + 1;
            Integer luckyNum= luckyCan.get(randomNumber-1);
            luckyCan.remove(randomNumber-1);
            System.out.print(luckyNum+"\t");
            //mapping luckyNum to pos M , N
            int posN =  ( luckyNum % n );
            int posM =  (( luckyNum - posN) / n) +1;
            if (posN == 0){
                posN = n;
                posM = posM -1;
            }
            isT[posM][posN] = true;
            System.out.println(posM+"\t"+posN);
            selectedNum=selectedNum-1;
        }

        long endTime = System.currentTimeMillis();    // get end time ms
        long executionTime = endTime - startTime;     // cala execute time
        System.out.println("execute time: " + executionTime + " ms");

        //************************

        isT[4][1] = true;
        // printing part and the cases :
        for (int c = 1; c <= m; c++) {
            for (int r = 1; r <= n; r++) {
                if (!isT[c][r]) {
                    if (isT[c][r + 1]) v[c][r]++;
                    if (isT[c][r - 1]) v[c][r]++;
                    if (isT[c + 1][r]) v[c][r]++;
                    if (isT[c - 1][r]) v[c][r]++;
                    if (isT[c - 1][r + 1]) v[c][r]++;
                    if (isT[c - 1][r - 1]) v[c][r]++;
                    if (isT[c + 1][r + 1]) v[c][r]++;
                    if (isT[c + 1][r - 1]) v[c][r]++;
                }
                if (isT[c][r]) {
                    System.out.print(" * ");
                }
                else {
                    System.out.print(" " + v[c][r] + " ");
                }
            }
            System.out.println();
        }
    }
}

我做了一个映射

米 = 4 n = 6

我想将 2d 数组转换为 1d 线。

  • pos (1,1) = 行号 
    1
  • pos (4,3) = 行号 
    21
  1  2  3  4  5  6  
1 1  2  3  4  5  6  
2 7  8  9  10 11 12
3 13 14 15 16 17 18
4 19 20 21 22 23 24
  • 第1步：我创建一个luckyCan

我将所有行号（1到24）放入luckyCan中。

  • 第 2 步：从 luckyCan 获取随机行号

然后，当我从 luckyCan 获取随机行号时，它将从 luckyCan 中删除，直到 luckyCan 为空。

我不需要检测随机数是否重复。

  • 第 3 步：将行号映射到 2D 位置

如果我得到的第 17 行，则映射到 2D pos 是 (3,5)

  1  2  3  4  5  6  
1 1  2  3  4  5  6  
2 7  8  9  10 11 12
3 13 14 15 16 17 18
4 19 20 21 22 23 24
  • 第四步：设置 pos 为 True
isT[posM][posN] = true;

测试

我的代码：

  • 测试 1：
    50 50 2401
    => 
    48 ms
  • 测试 2：
    50 50 2490
    => 
    46 ms

您的代码：

  • 测试 1：
    50 50 2401
    => 
    68 ms
  • 测试 2：
    50 50 2490
    => 永无止境
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.