java - 算法未显示正确的输出

Question

问题是:

给你一个大小为 n × n 的二进制矩阵(即矩阵的每个元素为 0 或 1)。你想重新排列 1，使它们形成一个矩形区域。注意矩形区域应该只由1组成，整个矩阵的所有1都应该在这个矩形区域。

为了实现矩形区域，可以交换矩阵的任意两个元素。请找出所需的最少交换次数。如果无法以所需方式重新排列 1，请打印 -1。

输入

输入的第一行包含一个整数 T，表示测试用例的数量。 T 测试用例的描述如下。 每个测试用例的第一行将包含一个整数 n，表示矩阵的维数。 接下来的 n 行中的每一行都将包含 n 个空格分隔的整数，表示矩阵的第 i 行。

输出

对于每个测试用例，打印一行，其中包含一个整数，表示所需的最小交换次数或 -1，具体视情况而定。

示例

输入:

2

2

0 1

1 0

2

1 1 

1 0

输出:

1 

-1

解释

示例 1. 您可以将第二行第一列的 1 与第一行第一列的 0 交换。 交换后矩阵如下所示。

1 1 
0 0

这里所有的 1 形成一个 1 × 2 维的矩形区域。在这种情况下，将需要 1 次交换。

请注意，您也可以将第一行第二列的 1 与第二行第二列的 0 交换。 交换后的矩阵如下。

0 0
1 1 

所以在这种情况下你也需要 1 次交换。

总的来说，您需要 1 次交换。

示例 2。无法在 2 × 2 维矩阵中创建包含 3 个 1 的矩形区域，因此答案为 -1。

我的算法[编辑]

1. 首先我要从用户那里获取案例数
2. 然后是矩阵的阶[将是nxn阶]。
3. 所以逻辑是如果矩阵是 1x1 那么它只会打印 0
4. 否则，在从用户那里获取输入时 [只有 1 或 0] 我正在计算 1，因为我开发的逻辑是，当在奇数阶矩阵中时，1 将是偶数，那么它不能以矩形形式排列。并且对于矩阵的偶数阶，如果 1 是奇数，则无法排列。
5. 接下来我将遍历每个索引，如果我找到一个，然后我移动到下一个元素，否则我尝试在同一列中找到 1，如果没有找到我正在打破循环显示 -1 它不能以矩形形式排列
6. 在安排完一行之后，我会检查下一行是否已经安排好了，如果是的话，我会打破一切并转到下一个案例

n 矩形

我的解决方案

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;

public class Main {

    static long startTime;

    public static void main(String[] args) {


Scanner scanner = new Scanner(System.in);
            int numberOfOnes = 0;
            int T = scanner.nextInt();

            for (int t = 1; t <= T; t++) {
                int n = scanner.nextInt();

                int loopCounter, swapCounter = 0;
                boolean rowContainsZero = false;
                int array[][] = new int[n][n];
                boolean reject = true;
                //Worst and the most simpler conditions
                if (n == 1) {
                    System.out.print("0");
                    exitingSystem();
                }
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        array[i][j] = scanner.nextInt();
                        if (array[i][j] == 1) {
                            numberOfOnes++;
                        }
                    }
                }
                if (n % 2 == 0 && numberOfOnes % 2 != 0) {
                    System.out.println("-1");
                    if (t == T) {
                        exitingSystem();
                    }
                    continue;

                } else if (n % 2 != 0 && numberOfOnes % 2 == 0) {
                    System.out.println("-1");
                    if (t == T) {
                        exitingSystem();
                    }
                    continue;
                }
                //     System.out.println("Here i am");
                //From here swaping processes will take the place
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (array[i][j] == 1) {
                            continue;
                        } else if (array[i][j] == 0) {
                            loopCounter = i;
                            reject = true;
                            while (loopCounter < n) {
                                if (array[loopCounter][j] == 1) {
                                    int temp = array[loopCounter][j];
                                    array[loopCounter][j] = array[i][j];
                                    array[i][j] = temp;
                                    reject = false;
                                    swapCounter += 1;
                                    break;
                                }
                                loopCounter++;
                            }
                             if (rowContainsZero) {
                                System.out.println("" + swapCounter);
                                    break;
                            }
                            if (reject == true) {
                                System.out.println("-1");
                                break;
                            } else {
                                for (int m = i + 1; m < n; m++) {
                                    for (int k = 0; k < n; k++) {
                                        if (array[m][k] == 0) {
                                            rowContainsZero = true;
                                        } else {
                                            rowContainsZero = false;
                                            break;
                                        }
                                    }
                                }
                            }

                        } else {
                            System.out.println("0's and 1's were Expected :(");
                            exitingSystem();
                        }
                    }
                    if (reject == true) {
                        break;
                    }
                }
            }

    }

    public static void exitingSystem() {
        System.exit(0);
    }

}

但是 CODECHEF 计算机给出了错误的答案 + 他们也允许从键盘获取输入

Answer 1

我认为您的算法不完全正确。

我认为以下是您的第 4 步/奇数顺序 (n=3) 和偶数顺序 (numberOfOnes=4) 的反例:

1 1 0
1 1 0
0 0 0

这应该给出 0。 类似于 n=4 和 numberOfOnes=3:

1 1 1 0
0 0 0 0
0 0 0 0
0 0 0 0

这也应该给出 0。

我还没有深入分析你的第 5 步和第 6 步。

这里还有一些例子:

1 1 1 0
1 1 0 0
1 1 1 0
1 1 0 0

这应该给出 -1，因为从 10 个开始，您只能形成 2*5 或 1*10 形式的矩形，它们都不适合 4*4 框架。

1 1 1 0
1 1 0 0
1 1 1 0
1 0 0 0

这应该给出 1，因为通过将左下角的 1 向上和向右移动两个位置，您将得到一个 3*3 的矩形。