잔디 깍기 문제입니다.

잔디밭(직사각형) (https://code.google.com/codejam/contest/2270488/dashboard#s=p1)

  1. 시작은 외곽에서부터 동작.
  2. 직선으로만 움직인다.
  3. 이동 도중에는 높이보다 높은 풀들은 잘라버린다.
  4. 끝에 가면 나가버린다.
  5. 박에서만 높이를 다시 설정할 수 있다.
  6. 도중에 잔디를 깍는도중 멈출수 없다.

예시는 다음과 같습니다.

Input 

3         ( case = 3 )
3 3       ( 1st case, 3x3)
2 1 2     
1 1 1
2 1 2
5 5       ( 2nd case, 5x5)
2 2 2 2 2
2 1 1 1 2
2 1 2 1 2
2 1 1 1 2
2 2 2 2 2
1 3        (3rd case, 1x3)
1 2 1
Output 
Case #1: YES
Case #2: NO
Case #3: YES
목표가 무엇인가요? - Flair Sizz, 2016/06/28 14:39 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

7개의 풀이가 있습니다.

가장 짧으면서 동일한 높이의 잔디 행과 열을 찾아 그 라인을 삭제함으로써 모든 라인이 삭제 가능하다면 YES 더이상 삭제 가능한 라인이 없다면 NO

input_string ="\
6\n\
3 3\n\
1 1 1\n\
2 2 2\n\
3 3 3\n\
3 3\n\
2 2 2\n\
1 1 1\n\
2 1 2\n\
3 3\n\
1 2 3\n\
1 2 3\n\
1 2 3\n\
3 3\n\
3 2 1\n\
3 2 1\n\
3 2 1\n\
7 7\n\
2 2 2 2 2 3 2\n\
2 1 1 1 2 3 1\n\
2 1 2 1 2 4 2\n\
2 1 1 3 2 4 2\n\
2 2 2 2 2 4 2\n\
2 2 2 2 2 4 2\n\
2 2 2 2 2 4 2\n\
20 10\n\
20 50 40 50 40 50 50 10 35 50\n\
20 50 40 50 40 50 50 10 35 50\n\
20 50 40 50 40 50 50 10 35 50\n\
15 15 15 15 15 15 15 10 15 15\n\
20 50 40 50 40 50 50 10 35 50\n\
20 30 30 30 30 30 30 10 30 30\n\
20 50 40 50 40 50 50 10 35 50\n\
20 25 25 25 25 25 25 10 25 25\n\
20 50 40 50 40 50 50 10 35 50\n\
20 25 25 25 25 25 25 10 25 25\n\
20 50 40 50 40 50 50 10 35 50\n\
15 15 15 15 15 15 15 10 15 15\n\
20 50 40 50 40 50 50 10 35 50\n\
20 10 10 10 10 10 10 10 10 10\n\
20 30 30 30 30 30 30 10 30 30\n\
10 10 10 10 10 10 10 10 10 10\n\
20 50 40 50 40 50 50 10 35 50\n\
20 50 40 50 40 50 50 10 35 50\n\
20 50 40 50 40 50 50 10 35 50\n\
20 40 40 40 40 40 40 10 40 40\n"


def checkLawns(nums):
    while(nums[0]):
        nROW, nCOL = len(nums), len(nums[0])

        while(nums):
            row = nums.index(min(nums))
            if len(set(nums[row])) == 1:
                del nums[row]
            else:
                break

        if not nums:
            return "YES"

        while (nums[0]):
            col = nums[0].index(min(nums[0]))
            if len(set([x[col] for x in nums])) == 1:
                for row in range(len(nums)):
                    del nums[row][col]
            else:
                break

        if (nROW, nCOL) == (len(nums), len(nums[0])):
            return "NO"

    return "YES"


def main(inputString):
    line = 1
    result = inputString.split('\n')

    for i in range(int(result[0])):
        nm = []
        nums = []
        nm = map(int , result[line].split(' '))
        for j in range(nm[0]):
            nums.append(map(int , result[j+line+1].split(' ')))
        line += nm[0] + 1

        print "Case #%d %s" %(i+1, checkLawns(nums))


main(input_string)
Case#1 YES
Case#2 NO
Case#3 YES
Case#4 YES
Case#5 NO
Case#6 YES
+1 case#6 에 입력데이터 보면 첫줄 8번째 데이터가 35인데요, 그거 깍을 방법이 없는듯한데요.. 결과는 YES로 나왔네요. - 상파, 2016/01/22 00:53 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
    Sub Main()
        Dim input() As Integer = Array.ConvertAll(Split(Console.ReadLine, " "), Function(d As String) CInt(d))
        Dim map(input(0) - 1)() As Byte

        For x As Integer = 0 To input(0) - 1
            map(x) = Array.ConvertAll(Split(Console.ReadLine, " "), Function(d As String) CByte(d))
        Next

        Dim n As Integer = 0
        Dim l As Byte = map.Aggregate(
            Function(m() As Byte, mm() As Byte)
                If m(0) < mm(0) Then
                    Return m
                Else
                    Return mm
                End If
            End Function).Min

        For y As Integer = 0 To map.Length - 1
            For x As Integer = 0 To map(y).Length - 1
                If map(y)(x) > l Then
                    map(y)(x) = l
                    n += 1
                End If
            Next
        Next

        Console.WriteLine("Result: " & {"YES", "NO"}(CInt(n > 0) + 1))

        Console.ReadLine()
    End Sub
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#-*- coding: utf-8 -*-
total_case = input()
case =[]
for i in range(total_case):
    row, column = map(int, raw_input().split())
    each_case =[]
    for j in range(row):
        each_case.append(list(map(int, raw_input().split())))
    case.append(each_case)
'''
잔디밭위의 모든 점을 검사하되,
그 점이 속해있는 행과 열의 최대값이 모두 그 점보다 높으면
그점은 깍기가 불가능합니다.
'''
for case_num,each_case in enumerate(case):
    result = 'YES'
    for i in range(len(each_case)):
        for j in range(len(each_case[i])):
            x = each_case[i][j]
            if max(each_case[i])>x and\
                max(each_case[t][j] for t in range(len(each_case)))>x:
                print i,j
                result ='NO'
                break
        if result == 'NO' : break
    print 'Case #%d:%s'%(case_num+1, result)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

진행하는 방향의 옆에서 단면을 봤을 때 #__# 이렇게 되면 깎을 수가 없는 패턴입니다. 이 때 직각 방향으로 깎아서 속을 파내(?)는 게 가능하다면 괜찮겠지만, 아래 위로도 자기보다 키큰 풀이 이미 있다면 깎을 수가 없는 포인트가 됩니다. 즉 양옆으로의 최대높이와 아래위로의 최대높이가 모두 자기보다 큰 값이 존재한다면 깎을 수 없다고 판정합니다.


def do(w, h, matric):
    for _ in range(h):
        matric += [int(x) for x in input().split()][:w]

    for i in range(w*h):
        rMax = max([matric[(i // w) * w + x] for x in range(w)])
        cMax = max([matric[(i % w) + (x * w)] for x in range(h)])
        if matric[i] < rMax and matric[i] < cMax:
            print(i % w, i // w, i, matric[i], rMax, cMax)
            return False
    return True

n = int(input())
for _ in range(n):
    w, h = [int(x) for x in input().split()][:2]
    data = []
    for _ in range(h):
        data += [int(x) for x in input().split()][:w]
    if do(w, h, data):
        print("YES")
    else:
        print("NO")
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C#으로 작성했습니다. matrix 안의 모든 숫자를 돌면서 위아래로 way-out이 없을 때 false를 출력합니다.

        public bool IsLawnmower(int[,] input)
        {
            for(int i = 0; i < input.GetLength(0); i++)
            {
                for (int j = 0; j < input.GetLength(1); j++)
                {
                    var curr = input[i, j];
                    for (int k = 0; k < input.GetLength(1); k++)
                    {
                        if (input[i, k] <= curr) continue;
                        for (int l = 0; l < input.GetLength(0); l++)
                            if (input[l, j] > curr) 
                                return false;
                    }
                }
            }
            return true;
        }
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

설명이 보충되면 좋겠네요(시작위치, 외곽, 밖, 높이설정). 풀이는 쉬운데 문제해독이 어려웠습니다.

row =  ->y { gets.split.map.with_index {|h,x| [y,x,h] } }
lawns = proc { (1..gets.to_i).map { (1..gets.to_i).flat_map(&row) } }
clean = ->m { m.any? {|ex,ey,ev| m.any? {|x,_,v|x==ex && v>ev} && 
                                 m.any? {|_,y,v|y==ey && v>ev} } ? "NO" : "YES" }
mown = ->lawns { puts lawns.map.with_index {|m,n| "Case ##{n+1}: #{clean[m]}" } }

Test

case_yes = [[0, 0, "1"], [0, 1, "2"], [0, 2, "1"]]
case_no  = [[0, 0, "1"], [0, 1, "2"], [1, 0, "2"], [1, 1, "1"]]
expect( clean[case_yes] ).to eq "YES"
expect( clean[case_no ] ).to eq "NO"

stdin_lawns = "3\n" + 
              "3 3\n" +
              "2 1 2\n" +
              "1 1 1\n" +
              "2 1 2\n" +
              "5 5\n" +
              "2 2 2 2 2\n" +
              "2 1 1 1 2\n" +
              "2 1 2 1 2\n" +
              "2 1 1 1 2\n" +
              "2 2 2 2 2\n" +
              "1 3\n" +
              "1 2 1\n"
expected =  "Case #1: YES\n" +
            "Case #2: NO\n" +
            "Case #3: YES\n"
$stdin = StringIO.new(stdin_lawns)
expect{ mown[lawns[]] }.to output( expected ).to_stdout

Output

#=> mown.( lawns[] )    # stdin input case
#=> mown.( lawns[...] ) # array input case
Case #1: YES
Case #2: NO
Case #3: YES
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
case_list = [[list(map(int,input().split(' '))) for x in range(int(input()))] for y in range(int(input()))]
count,_max,result = 0,0,['YES' for x in range(len(case_list))]
for case in case_list:
    for x in range(len(case)):
        test = [a[x] for a in case]
        if min(test[1:len(test)-1]) < test[0] and min(test[1:len(test)-1]) < test[-1] or \
           min(case[1:len(case)-1]) < case[0] and min(case[1:len(case)-1]) < case[-1]:
            result[count] = 'NO'
    count += 1
for x in range(len(result)):
    print('#%d: %s' % (x+1,result[x]))

#### 2017.01.31 D-387 ####

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 7
python x 4
cs x 1
기 타 x 1
ruby x 1