藍橋杯 基礎練習VIP 晶片測試 java

題目

題目描述

有n（2≤n≤20）塊晶片，有好有壞，已知好晶片比壞晶片多。

每個晶片都能用來測試其他晶片。用好晶片測試其他晶片時，能正确給出被測試晶片是好還是壞。而用壞晶片測試其他晶片時，會随機給出好或是壞的測試結果（即此結果與被測試晶片實際的好壞無關）。

給出所有晶片的測試結果，問哪些晶片是好晶片。

輸入

輸入資料第一行為一個整數n，表示晶片個數。

第二行到第n+1行為n*n的一張表，每行n個資料。表中的每個資料為0或1，在這n行中的第i行第j列（1≤i, j≤n）的資料表示用第i塊晶片測試第j塊晶片時得到的測試結果，1表示好，0表示壞，i=j時一律為1（并不表示該晶片對本身的測試結果。晶片不能對本 身進行測試）。

輸出

按從小到大的順序輸出所有好晶片的編号

樣例輸入

3

1 0 1

0 1 0

1 0 1

樣例輸出

1 3

代碼

https://blog.csdn.net/qq_34525938/article/details/79105343

複雜

import java.io.IOException;
import java.util.Scanner;

public class Main {
	static int[][] input;
	static boolean maodun = false;
	static int[] judge;// 判斷數組
	static int n;
	
	public static void main(String[] args) throws IOException{
		Scanner scanner = new Scanner(System.in);
	    n = scanner.nextInt();//晶片個數
	    input = new int[n + 1][n + 1]; // 初始化
		judge = new int[n + 1];
		for (int i = 1; i < n + 1; i++) // -1表示未使用，1表示good，2表示bad
			judge[i] = -1;
 
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				input[i][j] = scanner.nextInt();
 
		
		int index=1;
		for (int i = 1; i <= n; i++) 
		{
			put(i, 1);
			if(!maodun&&judge())//如果沒有沖突并且滿足半數條件
			{
				index=i;    //第i個晶片是正确的
				break;
			}
		}
 
		for (int i = 1; i < n + 1; i++)
			if(input[index][i]==1)
			   System.out.print(i+" ");
	}
 
	private static boolean judge() {// 判斷1的個數是否超過半數
		int count = 0;
		for (int i = 1; i <= n; i++) 
		{
			if (judge[i] == 1)
				count++;
		}
		if (count > n / 2)
			return true;
		
		
		for (int i = 1; i < n + 1; i++) // 再次初始化judge -1表示未使用，1表示good，2表示bad
			judge[i] = -1;
		
		return false;
	}
 
	private static void put(int i, int j) {
		maodun = false;// 防止遞歸操作受上一次影響
 
		if (judge[i] != j && judge[i] != -1)// 如果産生了沖突
		{
			maodun = true;
			return;
		}
 
		if (judge[i] == j)// 如果已經放置
			return;
 
		judge[i] = j; // 放置
 
		for (int k = 1; k < input[0].length; k++) 
		{
			if (input[i][k] == 1)
				put(k, input[i][k]);
        }
    }
}