acm-2008-B-Painting

acm-2008-B-Painting

Problem B: Painting
Ethan wants to draw a painting on an m×n board. He can draw some strips on the board using a paintbrush of width one. In each step, he must choose a new color and paint a full column or a full row.
He has a great image to be drawn on the board, but he doesn’t know which color to use first. You must help him in finding out the order of colors.

Input (Standard Input)
There are multiple test cases in the input. The first line of each test case contains two integers m and n, the size of the board (0< m, n <100). Following the first line, there are m lines with n integers denoting the color in each cell. All the colors are positive integer numbers less than 10000. The input is terminated with a single line containing two consecutive zeros.

Output (Standard Output)
For each test case, write a single line containing the order of colors used to paint the board. If there are several answers, output the one which is lexicographically smallest (considering each number as a symbol).

Sample Input and Output

Standard OutputStandard Input
1 3 4 6 5 2
2 3 1
4 4
1 5 4 3
6 5 6 6
2 2 2 2
1 5 4 3
3 2
1 1
2 3
2 3
0 0

سوال ب: رنگ آمیزی

اتان یک برد با ابعاد m x n را می خواهد رنگ کند. او می تواند صفحه را با استفاده از یک برس رنگی به عرض یک واحد رنگ کند. در هر مرحله، باید یک رنگ جدید بر دارد و یک سطر یا ستون را به صورت کامل رنگ کند. او یک تصویر از نقاشی تکمیل شده دارد ولی نمی داند که باید از کدام رنگ شروع به کار کند. شما باید به او کمک کنید که ترتیب رنگ را متوجه شود.

ورودی

تعدادی تست موردی در ورودی وجود دارد. اولین خط از هر تست موردی شامل دو عدد m , n می شود که اندازه برد را نشان می دهد که اعداد بین 0 تا ۱۰۰ می باشند. در ادامه خط اول، m خط با n ستون علامت گذاری شده وجود دارد.تمام رنگ ها باید از 10000 کوچکتر باشند. ورودی با یک خط که شامل دو 0 می باشد به پایان می رسد.

خروجی

برای هر تست موردی، یک خط که شامل ترتیب رنگ هایی که باید استفاده شود را بنویسید. اگر شما چند راه پیدا کردید، باید کوچکترین عددی را که در بین آنها هست چاپ کنید.

نمونه ای از ورودی و خروجی

خروجیورودی
1 3 4 6 5 2
2 3 1
4 4
1 5 4 3
6 5 6 6
2 2 2 2
1 5 4 3
3 2
1 1
2 3
2 3
0 0

راه حل:

نکته: الگوریتم به این صورت هست که باید سطر یا ستونی را که به صورت کامل هست را در stack بگذاریم و آن سطر یا ستون را حذف کنیم و دوباره این کار را با ماتریس جدید انجام دهیم.

package acm2008;

import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import util.AcmUtil;

public class acm2008b {
	
	public static void main(String[] args) {
		int m,n;
		int fileContentIndex = 0;
		String input = "E:\\acm\\2008\\TD87\\b.in";
		String output = "E:\\acm\\2008\\TD87\\b.out";
		String myOutput = "E:\\acm\\2008\\TD87\\b-my.out";
		
		List<String> fileContent = AcmUtil.readFromFile(input);
		List<String> outputList = new ArrayList<String>();
		do {
			Integer[] size = getMatrixSize(fileContent, fileContentIndex++);
			m = size[0];
			n = size[1];
			if (m == 0 || n == 0)
				break;
			
			int[][] matrixData = getMatrixData(fileContent.subList(fileContentIndex, fileContentIndex + m), m, n);
			fileContentIndex += m;
			
			
			Stack<Integer> stack = new Stack<Integer>();
			while (matrixData.length > 0) {
				
				if (n == 1 && m > 1) {
					int[] columnData = getColumnMatrix(matrixData, 0);
					int uniqueNum = getUniqueNum(columnData);
					stack.push(uniqueNum);
					matrixData = removeRow(matrixData, uniqueNum);
					m--;
				} else {
					//row
					List<Integer> sameRowDataList = new ArrayList<Integer>();
					//get row duplicate number
					for (int[] rowData : matrixData) {
						if (isAllSameNumber(rowData, rowData[0]) && !sameRowDataList.contains(rowData[0])) {
							sameRowDataList.add(rowData[0]);
						}
					}
					
					if (sameRowDataList.size() > 0) {
						for (Integer sameData : sameRowDataList) {
							matrixData = removeRow(matrixData, sameData);
							m--;
						}
					}
					
					addToStack(stack, sameRowDataList);
				}
				
				if (m == 1 && n > 1) {
					int[] rowData = matrixData[0];
					int uniqueNum = getUniqueNum(rowData);
					stack.push(uniqueNum);
					matrixData = removeColumn(matrixData, uniqueNum);
					n--;
				} else {
					//column
					List<Integer> sameColumnDataList = new ArrayList<Integer>();
					if (matrixData.length > 0) {
						//get column duplicate number
						for (int columnNum=0; columnNum < n; columnNum++) {
							int[] matrixColumnData = getColumnMatrix(matrixData, columnNum);
							if (isAllSameNumber(matrixColumnData, matrixColumnData[0]) && !sameColumnDataList.contains(matrixColumnData[0])) {
								sameColumnDataList.add(matrixColumnData[0]);
							}
						}
						
						if (sameColumnDataList.size() > 0) {
							for (Integer sameData : sameColumnDataList) {
								matrixData = removeColumn(matrixData, sameData);
								n--;
							}
						}
					}
					
					addToStack(stack, sameColumnDataList);
				}
				
			}
			
			
			printStack(stack, outputList);
		} while(m != 0 || n != 0);
		
		writeToFile(outputList, myOutput);
		
		
		System.out.println(AcmUtil.diffFile(output, myOutput));
	}

	private static void addToStack(Stack<Integer> stack, List<Integer> sameColumnDataList) {
		Collections.sort(sameColumnDataList);
		Collections.reverse(sameColumnDataList);
		for (Integer sameData : sameColumnDataList) {
			stack.push(sameData);
		}
	}

	private static void writeToFile(List<String> outputList, String pathFileName) {
		try {
			FileWriter writer = new FileWriter(pathFileName); 
			for(String str: outputList) {
			  writer.write(str + System.lineSeparator());
			}
			writer.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private static boolean isAllSameNumber(int[] arr, int num) {
		boolean isSame = true;
		for (int i : arr) {
			if (i != num)
				isSame = false;
		}
		return isSame;
	}
	
	public static int[][] removeRow(int[][] matrixData, int deleteNum) {
		if (matrixData.length > 0) {
			int row = matrixData.length;
		    int col = matrixData[0].length;
	
		    int [][] newArray = new int[row-1][col]; //new Array will have one column less
	
	
		    boolean isValidArray = false;
		    for (int j=0; j < col; j++) {
		    	int newRow = 0;
		    	for (int i=0; i < row; i++) {
		    		if (matrixData[i][j] != deleteNum) {
		    			newArray[newRow++][j] = matrixData[i][j];
		    			isValidArray = true;
		    		}
		    	}
		    }
	
		    if (isValidArray)
		    	return newArray;
		}
	    return new int[][] {};
		
	}
	
	public static int[][] removeColumn(int[][] matrixData, int deleteNum) {
		if (matrixData.length > 0) {
			int row = matrixData.length;
		    int col = matrixData[0].length;
	
		    int [][] newArray = new int[row][col-1]; //new Array will have one column less
	
	
		    boolean isValidArray = false;
		    for (int i=0; i < row; i++) {
		    	int newCol = 0;
		    	for (int j=0; j < col; j++) {
		    		if (matrixData[i][j] != deleteNum) {
		    			newArray[i][newCol++] = matrixData[i][j];
		    			isValidArray = true;
		    		}
		    	}
		    }
	
		    if (isValidArray)
		    	return newArray;
		}
	    return new int[][] {};
	}
	
	public static int[] getColumnMatrix(int[][] matrix, int column) {
	    return IntStream.range(0, matrix.length).map(i -> matrix[i][column]).toArray();
	}
	
	public static void printStack(Stack<Integer> stack, List<String> outputList) {
		String output = "";
		while (stack.size() != 0) {
			output += (stack.pop() + " ");
		}
		if (output != null && output.length() > 0) {
			output = output.substring(0, output.length()-1);
			outputList.add(output);
		}
	}
	
	
	
	public static int getUniqueNum(int[] arr) {
		List<Integer> uniqueList = new ArrayList<Integer>();
		for (int i : arr) {
			int count = 0;
			for (int j : arr) {
				if (i == j)
					count++;
			}
			if (count == 1)
				uniqueList.add(i);
		}
		if (uniqueList != null && uniqueList.size() > 0) {
			Collections.sort(uniqueList);
			Collections.reverse(uniqueList);
			return uniqueList.get(0);
		}
		return 0;
	}
	
	public static Integer[] getMatrixSize(List<String> fileContent, int fileContentIndex) {
		String mn = fileContent.get(fileContentIndex);
		Integer spaceIndex = mn.indexOf(" ");
		int m = Integer.parseInt(mn.substring(0,spaceIndex));
		int n = Integer.parseInt(mn.substring(spaceIndex+1));
		return new Integer[] {m , n};
	}
	
	public static int[][] getMatrixData(List<String> fileContent, int m, int n) {
		int[][] matrixData = new int[m][n];
		int count = 0;
		for (String rowStr : fileContent) {
			int[] row = getRowMatrixData(rowStr);
			matrixData[count] = row;
			count++;
		}
		return matrixData;
	}
	
	public static int[] getRowMatrixData(String rowWithSpace) {
		List<String> stringData = Arrays.asList(rowWithSpace.split(" "));
		List<Integer> intData = stringData.stream().map(Integer::valueOf).collect(Collectors.toList());
		return intData.stream().mapToInt(i->i).toArray();
	}
	

}

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *