exceeding time limit in a minesweeper program

Question

**The Assignment : **

Minesweeper is a 1960s era video game played on an m-by-n grid of cells. The goal is to deduce which cells contain hidden mines using clues about the number of mines in neighboring cells. Write a program Minesweeper.java that takes three integer command-line arguments m, n, and k and prints an m-by-n grid of cells with k mines, using asterisks for mines and integers for the neighboring mine counts (with two space characters between each cell). To do so,

**The Desired Output : **

**The Problem : **

when I put k number close to m * n , the desired output won't be printed (it takes loooong time to generate a different index look at the code below to understand what I mean) .

this the full code :

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();
        }
    }
}

note : I think the cause of the problem is the two random numbers I tried to figure out another solution that doesn't use randoms but I failed .

Answer 1

Your Code Block

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);
}

I've changed the code here to find a few things better.

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

application input parameter: 8 4 31

Your code never ends.

Because there is an error in your code:

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

input m=8 , n=4 , k=31

• but your first num (m) always 1~7 , not include 8.
• and your second num (n) always 1~3, not include 4.

your code always fill 7 * 3 = 21, but when you put k=31, it never reaches 31.

you can test your input.

• input 8 4 21 ( 21 = 7 x 3) , your code will run very fast.

• input 8 4 22 ( 22 = 21+1, 21 = 7 x 3) , it will never end. (your code always get random (1~7),(1~3), never get row column 8,4)

This is the root cause.

Your array start from 1 not from 0.

But when you set column or row, the length is -1

then correct range:

m (1~8), n(1~4).

but your code range:

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

When K <= your code range (7 * 3), work fine. But when K > your code range (7 * 3), then while loop never end.

CORRECT CODE

while (countofMinesSweeper < k) {
    //int mrand = (int) ((Math.random() * (m - 1))) + 1; // 1 => m
    //int nrand = (int) ((Math.random() * (n - 1))) + 1; // 1 => n
    int mrand = (int) ((Math.random() * (m))) + 1; // 1 => m
    int nrand = (int) ((Math.random() * (n))) + 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);
}