1-есептің шешімі

Блог аты dosbol
'#'-тар іші бүтін квадрат құрайма құрамайма табу керек.
5
4
..##
..##


4
..##
..##
#…

4
####
#..#
#..#
####
5
#####
#####
#####
#####

5
#####
#####
#####
#####
#####

осындай аутпут болу керек.
Case #1: YES
Case #2: NO
Case #3: NO
Case #4: NO
Case #5: YES

Яғни, сізге канша кейс бар екені берілет, сосын сонша кейс бар.
Ар кейста қанша жолдан тұратыны, және сонша жол '.' және '#' беріледі (әр жол ұзындығы жолдар санына тең NxN)
сол кейстегі '#'-тар іші толық квадрат берсе YES әйтпесе NO

You want to write an image detection system that is able to recognize different geometric shapes. In the first version of the system you settled with just being able to detect filled squares on a grid.
You are given a grid of N×N square cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape.
Input
The first line of the input consists of a single number T, the number of test cases.
Each test case starts with a line containing a single integer N. Each of the subsequent N lines contain N characters. Each character is either "." symbolizing a white cell, or "#" symbolizing a black cell. Every test case contains at least one black cell.
Output
For each test case i numbered from 1 to T, output «Case #i: », followed by YES or NO depending on whether or not all the black cells form a completely filled square with edges parallel to the grid of cells.
Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 20
Example
Test cases 1 and 5 represent valid squares. Case 2 has an extra cell that is outside of the square. Case 3 shows a square not filled inside. And case 4 is a rectangle but not a square.

package hack2014;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Square {
	static Scanner sc;
	/**
	 * @param args
	 * @throws FileNotFoundException 
	 */
	public static void main(String[] args) throws FileNotFoundException {
		
		sc = new Scanner(new File("C:\\Users\\user\\Desktop\\eclipse\\facebook\\input.txt"));
		
		int T = sc.nextInt();
		
		for (int i = 0; i < T; i++) {
			iterations(sc,i);
		}

	}
	private static void iterations(Scanner sc, int cases) {
		int N = sc.nextInt();
		char[][]array = new char[N][N];
		sc.nextLine();
		for (int i = 0; i < N; i++) {
			array[i] = sc.nextLine().toCharArray();
		}
		
		answer(array, cases);
	}
	
	private static void answer(char[][] array, int cases) {
		
		System.out.print("Case #"+(cases+1)+": ");
		
		boolean isFirst=false;//when we first reach '#'
		boolean isSecond=false;//when we reach other than'#'||end of column
		int firstPointI=0,firstPointJ=0;
		int secondPointI=0,secondPointJ=0;
		//main logic
		outer:
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array.length; j++) {
				if (array[i][j]=='#') {
					if(!isFirst){
						firstPointI=i;
						firstPointJ=j;
						isFirst=true;
					}
				}else if(!isSecond && isFirst){//we got '#' early and now not '#'
					secondPointJ=j-1;
					secondPointI=i+(secondPointJ-firstPointJ);
					isSecond=true;
					break outer;
				}
			}
			if(isFirst && !isSecond){//we got '#' early and now end of column
				secondPointJ=array.length-1;
				secondPointI=i+secondPointJ-firstPointJ;
				break outer;
			}
		}
		
		if(isArrayFilled(array, firstPointI, secondPointI, firstPointJ, secondPointJ)
				&& isThereOtherSharp(array, firstPointI, secondPointI, firstPointJ, secondPointJ)
				){
			System.out.println("YES");
		}else{
			System.out.println("NO");
		}
	}
	
	private static boolean isArrayFilled(char[][] array,int i1,int i2,int j1,int j2) {
		for (int i = i1; i <= i2; i++) {
			for (int j = j1; j <=j2; j++) {
				if(array[i][j]!='#')
					return false;
			}
		}
		return true;
	}
	private static boolean isThereOtherSharp(char[][] array,int i1,int i2,int j1,int j2) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j <array.length; j++) {
				if(array[i][j]=='#' && (i<i1 || i>i2 || j<j1 || j>j2))
					return false;
			}
		}
		return true;
	}
}

0 пікір

Тек қана тіркелген және авторизациядан өткен қолданушылар пікір қалдыра алады.