acm-2008-C-Another Brick in the Wall

acm-2008-C-Another Brick in the Wall

Problem C: Another Brick in the Wall

After years as a brick-layer, you’ve been called upon to analyze the instability of brick walls. The instability of a wall
can be approximated by the maximum damage to a wall in case of taking one brick out. A brick will fall if all bricks
that are directly underneath it are removed. Note that if the space underneath a brick is partially empty, it does not fall.
You are given the description of all bricks in a wall, and must determine the instability of the wall as described in the
following sections.

Input (Standard Input)

There are multiple test cases in the input. Each test case consists of a single line, “M N” (1 ≤ M, N ≤ 100) where M and
N indicate the height and width (in units), respectively, of the input wall.
Each of the next M lines is a string of N digits which specifies a row in the wall. Each brick in a row is represented by a
substring of the row (like s) such that every digit in s is the same, which is equal to the length of s too. For example, 333 and 22 are two bricks of length 3 and 2 respectively, but 111 specifies three bricks of length one. A 0 in a row means there is no brick in that place of wall. Note that the height of each brick is one. The input terminates with a line
containing 0 0. You may assume that the input is correct. This means:
1) There is no brick such that the length of the brick does not conform to the digits in the brick (like 222 in the row 12221).
2) No brick can fall initially.

Output (Standard Output)

For each test case, write a single line containing maximum sum of the bricks’ lengths that will fall if we take one brick
out (including that brick).

Sample Input and Output

Standard OutputStandard Input
5
8
4
4 5
33322
22333
33322
22333
4 6
122333
444422
111111
333333
3 3
022
220
111
0 0

سوال پ: آجری دیگر در دیوار

بعد از سالها دیوارچینی آجر، از شما خواسته شده که بی ثباتی دیوارهای آجری را تجزیه و تحلیل کنید. عدم ثبات یک دیوار را می توان با حداکثر آسیبی که با برداشته شدن یک آجر وارد می شود را تخمین زد. یک آجر زمانی می افتد که تمام آجرهای زیر آن حذف شده باشند. توجه داشته باشید که اگر فضای زیر آجر تا حدی خالی باشد، نمی افتد. به شما شرح تمام آجرهای یک دیوار داده شده است، باید بی ثباتی دیوار را با استفاده از قوانین بخش زیر تعیین کنید.

ورودی

تعدادی تست موردی در ورودی وجود دارد. هر تست موردی یک خط برای “M N” دارد که این دو عدد طول و عرض را مشخص می کنند.

برای M خط بعدی، رشته هایی دارای N عدد وجود دارند که معرف یک سطر از دیوار می باشند. هر آجر در یک ردیف توسط یک زیر رشته (مانند s) معرفی می شود که تمام اعداد در s مشابه هم هستند و برابر طول s هم هست. برای مثال، 333 و 22 دو آجر هستند که به ترتیب طول آنها ۳ و ۲ است ولی 111 سه آجر جدا از هم با طول ۱ است. یک 0 در سطر نشان می دهد که هیچ آجری در آن منطقه نیست. توجه داشته باشید که ارتفاع هر آجر یک است. ورودی با خطی که شامل 0 0 می باشد به پایان می رسد. شما می توانید فرض کنید که ورودی درست است. این یعنی:

  1. هیچ آجری وجود ندارد که طول آجر با اعداد در آجر مطابقت نداشته باشد (مثل 222 در سطر 12221)
  2. در ابتدا هیچ آجری نمی تواند سقوط کند

خروجی

برای هر تست موردی، یک خط بنویسید که شامل حداکثر مجموع طول آجرها باشد که اگر یک آجر را برداریم سقوط می کند (از جمله آن آجر)

Standard OutputStandard Input
5
8
4
4 5
33322
22333
33322
22333
4 6
122333
444422
111111
333333
3 3
022
220
111
0 0
package acm2008;

import java.util.ArrayList;
import java.util.List;

import util.AcmUtil;

public class acm2008c {
	
	public static void main(String[] args) {
		int m,n;
		int fileContentIndex = 0;
		String input = "E:\\acm\\2008\\TD87\\c.in";
		String output = "E:\\acm\\2008\\TD87\\c.out";
		String myOutput = "E:\\acm\\2008\\TD87\\c-my.out";
		
		List<String> fileContent = AcmUtil.readFromFile(input);
		List<String> outputList = new ArrayList<String>();
		do {
			Integer[] size = AcmUtil.getMatrixSize(fileContent, fileContentIndex++);
			m = size[0];
			n = size[1];
			if (m == 0 || n == 0)
				break;
			
			String[][] matrixData = AcmUtil.getMatrixDataString(fileContent.subList(fileContentIndex, fileContentIndex + m), m, n);
			fileContentIndex += m;
			
			int row = m-1;
			int col = 0;
			int maxBrickFall = 0;
			
			while (col <= n && row > 0) {
				int brickLength = getBufferSize(matrixData, row, col);
				if (col + brickLength <= n &&  brickLength > 0) {
					// left 0
					int rightZero = getRightZero(matrixData, col, row, brickLength);
					//right 0
					int leftZero = getLeftZero(matrixData, col, row);
					
					brickLength += leftZero + rightZero;
					
					String[] buffer = new String[brickLength];
					fillBuffer(buffer, "#");
					
					
					int currentBrickFall = 0;
					int up = 0;
					while (brickLength > 0 && row - up >= 0) {
						String[] topLine = getDataLine(matrixData, row - up, col - leftZero, brickLength);
						setBrickInBeffer(brickLength, buffer, topLine);
						currentBrickFall += removeIncompleteBrickAndGetLength(buffer);
						brickLength = getBrickLengthInBuffer(buffer);
						up++;
					}
					
					
					
					if (maxBrickFall < currentBrickFall)
						maxBrickFall = currentBrickFall;
					
					col += buffer.length;
				} else {
					col++;
				}
				
				
				// end of wall
				if (col >= n) {
					col = 0;
					row -= 1;
				}
					
			}
			
			//System.out.println(maxBrickFall);
			outputList.add("" + maxBrickFall);
			
		} while(m != 0 || n != 0);
		
		AcmUtil.writeToFile(outputList, myOutput);
		System.out.println(AcmUtil.diffFile(output, myOutput));
	}

	private static int getBufferSize(String[][] matrixData, int row, int col) {
		int totalBrickLength = 0;
		int brickLength = Integer.parseInt(matrixData[row][col]);
		totalBrickLength += brickLength;
		
		return totalBrickLength;
	}
	
	private static int getRightZero(String[][] matrixData, int col, int row, int totalBrickLength) {
		int rightZero = 0;
		int rightIndex = 0;
		int endOfBrick = col + totalBrickLength;
		int count = 0;
		while (rightZero == 0 && endOfBrick + rightIndex < matrixData[0].length) {
			rightZero = Integer.parseInt(matrixData[row][endOfBrick + rightIndex]);
			if (rightZero == 0)
				count++;
			rightIndex++;
		}
		return count;
	}
	
	private static int getLeftZero(String[][] matrixData, int col, int row) {
		int leftIndex = 1;
		int rightZero = 0;
		int totalBrickLength = 0;
		while (rightZero == 0 && col - leftIndex >= 0) {
			rightZero = Integer.parseInt(matrixData[row][col - leftIndex]);
			if (rightZero == 0)
				totalBrickLength++;
			leftIndex++;
		}
		return totalBrickLength;
	}
	
	private static void setBrickInBeffer(int brickLength, String[] buffer, String[] topLine) {
		fillBuffer(buffer, "#");
		for (int i = 0; i < brickLength; i++) {
			buffer[i] = topLine[i];
		}
	}
	
	private static String[] getDataLine(String[][] matrixData, int rowNum, int colNum, int length) {
	    String rowData = String.join("", matrixData[rowNum]);
	    //System.out.println(rowData + "   "  + colNum + "   "  +  colNum + length);
	    int first = colNum <= rowData.length() ? colNum : rowData.length();
	    int second = colNum + length <= rowData.length() ? colNum + length : rowData.length();
		return rowData.substring(first, second).split("");
	}
	
	private static void fillBuffer(String[] buffer, String data) {
		for (int i=0 ; i < buffer.length; i++) {
			buffer[i] = data;
		}
	}
	
	private static int removeIncompleteBrickAndGetLength(String[] buffer) {
		int length = 0;
		for (int i=0 ; i < buffer.length; i++) {
			if (!buffer[i].equals("#") && !buffer[i].equals("0")) {
				int size = Integer.parseInt(buffer[i]);
				size = size <= buffer.length ? size : buffer.length;
				boolean isBrickComplete = isCorrectBrick(buffer, i, size);
				if (isBrickComplete) {
					i += size - 1;
					length += size;
				} else {
					buffer[i] = "#";
				}
			}
		}
		return length;
	}
	
	public static int getBrickLengthInBuffer(String[] buffer) {
		int count = 0;
		for (String brick : buffer) {
			if (!brick.equals("#"))
				count++;
		}
		return count;
	}
	
	public static boolean isCorrectBrick(String[] row, int firstIndex, int brickSize) {
		int length = Integer.parseInt(row[firstIndex]);
		while (length == 0 && firstIndex < row.length - 1) {
			firstIndex++;
			length = Integer.parseInt(row[firstIndex]);
		}

		int y = (firstIndex + brickSize <= row.length) ? firstIndex + brickSize : row.length;
		String[] rowData = String.join("", row).substring(firstIndex, y).split("");
		
		if (length > rowData.length)
			return false;
		
		boolean isSame = true;
		String firstCharacter = rowData[0];
		for (String character : rowData) {
			if (!firstCharacter.equals(character))
				isSame = false;
		}
		
		return isSame;
	}
}


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

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