扫雷程序超时
Minesweeper program exceeding time limit
我正在学习普林斯顿大学在 cousera 上的课程,我针对以下问题编写了以下代码:
Minesweeper. 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,
Generate an m-by-n grid of cells, with exactly k of the mn cells containing mines, uniformly at random.
For each cell not containing a mine, count the number of neighboring mines (above, below, left, right, or diagonal).
每次提交给评分员;它说超过了 60 秒的限制,并停止评分。
这是期望的输出
public class Minesweeper {
public static void main(String[] args) {
int m = Integer.parseInt(args[0]);
int n = Integer.parseInt(args[1]);
int k = Integer.parseInt(args[2]);
boolean[][] minePositions = new boolean[m + 2][n + 2];
int[][] grid = new int[m + 2][n + 2];
int num = 0;
while (num != k) {
if ((m * n) == k) {
for (int f = 1; f <= m; f++) {
for (int z = 1; z <= n; z++) {
minePositions[f][z] = true;
}
}
break;
}
int r = (int) (Math.random() * (m * n - 1));
int q = r / n;
int rem = r % n;
if (q == 0) {
q = 1;
}
else if (q > (m - 1)) {
q = m - 1;
}
if (rem == 0) {
rem = 1;
}
else if (rem > (n - 1)) {
rem = n - 1;
}
if (!minePositions[q][rem]) {
minePositions[q][rem] = true;
num++;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (minePositions[i - 1][j + 1]) grid[i][j]++;
if (minePositions[i][j + 1]) grid[i][j]++;
if (minePositions[i + 1][j + 1]) grid[i][j]++;
if (minePositions[i - 1][j]) grid[i][j]++;
if (minePositions[i + 1][j]) grid[i][j]++;
if (minePositions[i - 1][j - 1]) grid[i][j]++;
if (minePositions[i][j - 1]) grid[i][j]++;
if (minePositions[i + 1][j - 1]) grid[i][j]++;
}
for (int j = 1; j <= n; j++) {
if (minePositions[i][j]) System.out.print("* ");
else System.out.print(grid[i][j] + " ");
}
System.out.print("\n");
}
}
}
我认为使用大小为 (m + 2, n + 2)
的数组会混淆您的数学运算。我会继续你的工作,在你的计算中总是使用 m + 2
和 n + 2
以避免任何混淆。
int r = (int) (Math.random() * ((m + 2) * (n + 2)));
生成一个可以跨越所有数组单元格的随机数。
int q = r / (n + 2);
int rem = r % (n + 2);
// Increment num only if q and rem are in the ranges and the position does not have a mine on it
if (q > 0 && q <= m && rem > 0 && rem <= n && !minePositions[q][rem]) {
minePositions[q][rem] = true;
num++;
}
完整代码
int m = Integer.parseInt(args[0]);
int n = Integer.parseInt(args[1]);
int k = Integer.parseInt(args[2]);
boolean[][] minePositions = new boolean[m + 2][n + 2];
int[][] grid = new int[m + 2][n + 2];
int num = 0;
while (num != k) {
int r = (int) (Math.random() * ((m + 2) * (n + 2)));
int q = r / (n + 2);
int rem = r % (n + 2);
if (q > 0 && q <= m && rem > 0 && rem <= n && !minePositions[q][rem]) {
minePositions[q][rem] = true;
num++;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (minePositions[i - 1][j + 1]) grid[i][j]++;
if (minePositions[i][j + 1]) grid[i][j]++;
if (minePositions[i + 1][j + 1]) grid[i][j]++;
if (minePositions[i - 1][j]) grid[i][j]++;
if (minePositions[i + 1][j]) grid[i][j]++;
if (minePositions[i - 1][j - 1]) grid[i][j]++;
if (minePositions[i][j - 1]) grid[i][j]++;
if (minePositions[i + 1][j - 1]) grid[i][j]++;
}
for (int j = 1; j <= n; j++) {
if (minePositions[i][j]) System.out.print("* ");
else System.out.print(grid[i][j] + " ");
}
System.out.print("\n");
}
我正在学习普林斯顿大学在 cousera 上的课程,我针对以下问题编写了以下代码:
Minesweeper. 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, Generate an m-by-n grid of cells, with exactly k of the mn cells containing mines, uniformly at random. For each cell not containing a mine, count the number of neighboring mines (above, below, left, right, or diagonal).
每次提交给评分员;它说超过了 60 秒的限制,并停止评分。
这是期望的输出
public class Minesweeper {
public static void main(String[] args) {
int m = Integer.parseInt(args[0]);
int n = Integer.parseInt(args[1]);
int k = Integer.parseInt(args[2]);
boolean[][] minePositions = new boolean[m + 2][n + 2];
int[][] grid = new int[m + 2][n + 2];
int num = 0;
while (num != k) {
if ((m * n) == k) {
for (int f = 1; f <= m; f++) {
for (int z = 1; z <= n; z++) {
minePositions[f][z] = true;
}
}
break;
}
int r = (int) (Math.random() * (m * n - 1));
int q = r / n;
int rem = r % n;
if (q == 0) {
q = 1;
}
else if (q > (m - 1)) {
q = m - 1;
}
if (rem == 0) {
rem = 1;
}
else if (rem > (n - 1)) {
rem = n - 1;
}
if (!minePositions[q][rem]) {
minePositions[q][rem] = true;
num++;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (minePositions[i - 1][j + 1]) grid[i][j]++;
if (minePositions[i][j + 1]) grid[i][j]++;
if (minePositions[i + 1][j + 1]) grid[i][j]++;
if (minePositions[i - 1][j]) grid[i][j]++;
if (minePositions[i + 1][j]) grid[i][j]++;
if (minePositions[i - 1][j - 1]) grid[i][j]++;
if (minePositions[i][j - 1]) grid[i][j]++;
if (minePositions[i + 1][j - 1]) grid[i][j]++;
}
for (int j = 1; j <= n; j++) {
if (minePositions[i][j]) System.out.print("* ");
else System.out.print(grid[i][j] + " ");
}
System.out.print("\n");
}
}
}
我认为使用大小为 (m + 2, n + 2)
的数组会混淆您的数学运算。我会继续你的工作,在你的计算中总是使用 m + 2
和 n + 2
以避免任何混淆。
int r = (int) (Math.random() * ((m + 2) * (n + 2)));
生成一个可以跨越所有数组单元格的随机数。
int q = r / (n + 2);
int rem = r % (n + 2);
// Increment num only if q and rem are in the ranges and the position does not have a mine on it
if (q > 0 && q <= m && rem > 0 && rem <= n && !minePositions[q][rem]) {
minePositions[q][rem] = true;
num++;
}
完整代码
int m = Integer.parseInt(args[0]);
int n = Integer.parseInt(args[1]);
int k = Integer.parseInt(args[2]);
boolean[][] minePositions = new boolean[m + 2][n + 2];
int[][] grid = new int[m + 2][n + 2];
int num = 0;
while (num != k) {
int r = (int) (Math.random() * ((m + 2) * (n + 2)));
int q = r / (n + 2);
int rem = r % (n + 2);
if (q > 0 && q <= m && rem > 0 && rem <= n && !minePositions[q][rem]) {
minePositions[q][rem] = true;
num++;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (minePositions[i - 1][j + 1]) grid[i][j]++;
if (minePositions[i][j + 1]) grid[i][j]++;
if (minePositions[i + 1][j + 1]) grid[i][j]++;
if (minePositions[i - 1][j]) grid[i][j]++;
if (minePositions[i + 1][j]) grid[i][j]++;
if (minePositions[i - 1][j - 1]) grid[i][j]++;
if (minePositions[i][j - 1]) grid[i][j]++;
if (minePositions[i + 1][j - 1]) grid[i][j]++;
}
for (int j = 1; j <= n; j++) {
if (minePositions[i][j]) System.out.print("* ");
else System.out.print(grid[i][j] + " ");
}
System.out.print("\n");
}