牛牛有一个n行m列的矩阵，每个格子里有一盏灯，灯有亮（1）和灭（0）两种状态。每次操作，牛牛可以选择一个格子，将其状态取反，同时，与这个格子相邻的上下左右四个格子（如果存在）的灯的状态也会被取反。请问牛牛至少需要进行多少次操作，才能使所有的灯都亮起来？
区块链毕设网qklbishe.com为您提供问题的解答
牛牛有一个n行m列的矩阵，每个格子里有一盏灯，灯有亮（1）和灭（0）两种状态。每次操作，牛牛可以选择一个格子，将其状态取反，同时，与这个格子相邻的上下左右四个格子（如果存在）的灯的状态也会被取反。请问牛牛至少需要进行多少次操作，才能使所有的灯都亮起来？
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int row = in.nextInt(); int col = in.nextInt(); // 消耗掉读取 row 和 col 后的换行符 in.nextLine(); StringBuilder sb = new StringBuilder(); // 读取矩阵的每一行 for (int i = 0; i < row; i++) { sb.append(in.nextLine().replace(" ", "")); } String str = sb.toString(); int[][] grid = new int[row][col]; // 将字符串转换为二维数组 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { int index = i * col + j; grid[i][j] = str.charAt(index) - '0'; } } int result = minFlips(grid); if (result == Integer.MAX_VALUE) { System.out.println("no solution"); } else { System.out.println(result); } } public static int minFlips(int[][] grid) { int n = grid.length; int m = grid[0].length; int minFlips = Integer.MAX_VALUE; // 枚举第一行的所有可能操作状态 for (int mask = 0; mask < (1 << m); mask++) { int[][] tmp = new int[n][m]; for (int i = 0; i < n; i++) { System.arraycopy(grid[i], 0, tmp[i], 0, m); } int count = applyFirstRow(tmp, mask); count += processRemainingRows(tmp); if (allLightsOn(tmp)) { minFlips = Math.min(minFlips, count); } } return minFlips; } private static int applyFirstRow(int[][] tmp, int mask) { int count = 0; for (int j = 0; j < tmp[0].length; j++) { if ((mask & (1 << j)) != 0) { toggle(tmp, 0, j); count++; } } return count; } private static int processRemainingRows(int[][] tmp) { int count = 0; for (int i = 1; i < tmp.length; i++) { for (int j = 0; j < tmp[i].length; j++) { if (tmp[i - 1][j] == 0) { toggle(tmp, i, j); count++; } } } return count; } private static boolean allLightsOn(int[][] tmp) { for (int[] row : tmp) { for (int light : row) { if (light == 0) { return false; } } } return true; } private static void toggle(int[][] tmp, int i, int j) { tmp[i][j] ^= 1; if (i > 0) tmp[i - 1][j] ^= 1; if (i < tmp.length - 1) tmp[i + 1][j] ^= 1; if (j > 0) tmp[i][j - 1] ^= 1; if (j < tmp[0].length - 1) tmp[i][j + 1] ^= 1; } }
15:03
以上就是关于问题牛牛有一个n行m列的矩阵，每个格子里有一盏灯，灯有亮（1）和灭（0）两种状态。每次操作，牛牛可以选择一个格子，将其状态取反，同时，与这个格子相邻的上下左右四个格子（如果存在）的灯的状态也会被取反。请问牛牛至少需要进行多少次操作，才能使所有的灯都亮起来？的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}