가장 짧으면서 동일한 높이의 잔디 행과 열을 찾아 그 라인을 삭제함으로써 모든 라인이 삭제 가능하다면 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

    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 ####

파이썬 3.6

"""
아이디어>
 1) 잔디깍기로 작업이 가능한 패턴은 잔디의 길이가 시작점(가장자리)부터 동일 직선상의 끝까지 같아야 합니다.
 2) 원하는 패턴의 가장자리 길이와 안쪽 길이가 다른 경우 잔디깍기로 패턴을 완성할 수 없습니다.
 3) 패턴이 똑같은 길이의 잔디로 된 직선으로만 구성되어 있는지 확인하여, 가능 여부를 판단합니다.
"""

def inputdata():
    case_list,case,tmp = [],[],[]
    T = int(input("T = "))
    for i in range(T):
        n,m = input('').split()
        for h in range(int(n)):
            tmp = input('').split()
            case.append(tmp)
            tmp = []
        case_list.append(case)
        case = []
    return case_list

def lawnmower(case):
    for n,value in enumerate(case):           
        for m in range(len(value)):
# 첫 행일 때, 각 열이 조건을 만족하는지 확인(세로 방향 이동)
            if n == 0 and m != 0 and m != len(value)-1:
                for t in range(len(case)):
                    if case[0][m] != case[t][m]:
                        return False
# 둘째 행 이후부터 각 행이 조건을 만족하는지 확인(가로 방향 이동)
            elif 0 < n < len(case)-1:
                if case[n][0] != case[n][m]:
                    return False
    return True

def main(case_list):
    count = 0
    for case in case_list:
        count += 1
        if lawnmower(case):
            print("Case #%d: Yes"%count)
        else:
            print("Case #%d: No"%count)

if __name__ == "__main__":
    case_list = inputdata()
    print("\n")
    main(case_list)

*결과값

T = 3 
3 3
2 1 2
1 1 1
2 1 2
5 5
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
1 2 1
Case #1: Yes
Case #2: No
Case #3: Yes

def garden(a, m, n):
    column = [[a[m*i+j] for i in range(n)]for j in range(m)]
    row = [[a[m*i+j] for j in range(m)] for i in range(n)]
    maximum_column = [max(i) for i in column]
    maximum_row = [max(i) for i in row]
    for i in range(m*n):
        if a[i] < maximum_row[i//m] and a[i] < maximum_column[i%n]:
            return 'NO'
    return 'YES'

def lawn_pos(pat):
    inp = [i.replace(' ','') for i in pat.split('\n')]
    for i in range(len(inp)):
        for j in range(len(inp[i])):
            if inp[i][j] != max(inp[i]) and inp[i][j] != max(inp[k][j] for k in range(len(inp))): return False
    return True

inp = '''\
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'''

print(lawn_pos(inp))

import numpy as np

raw_data = '''\
3
3 3
2 1 2     
1 1 1
2 1 2
5 5
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
1 2 1'''

def parse(raw_data):
    data = raw_data.split()
    for i in range(int(data.pop(0))):
        X, Y = int(data.pop(0)), int(data.pop(0))
        yield np.array([[int(data.pop(0)) for y in range(Y)] for x in range(X)]), X, Y


def _mowable(line, H):
    return all([h <= H for h in line])


def mowable(field, X, Y):
    for i in range(X):
        for j in range(Y):
            if not _mowable(field[i,:], field[i,j]) and not _mowable(field[:,j], field[i,j]):
                return 'No'

    return 'Yes'

for case, X, Y in parse(raw_data):
    print(mowable(case, X, Y))

어떤 위치의 높이보다 큰 높이가 같은 행에도 열에도 모두 존재한다면 그 높이로 깎을 수 없습니다. 4중 for문은 굳이 쓸 필요 없지만 읽기 더 편해보여 사용했습니다.

#include<iostream>
#include<array>
#include<vector>
#include<string>

using namespace std;

string solve(void)
{
    array<string,2> arrRet = {"YES", "NO"};
    int nRet = 0;
    int n, m;

    /// process input
    cin >> n >> m;
    vector<vector<int>> grassHeight(n, vector<int>(m));
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            cin >> grassHeight.at(i).at(j);
        }
    }

    /// determine whether it's possible
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            for(int k = 0; k < n; k++)
            {
                if(grassHeight.at(i).at(j) < grassHeight.at(k).at(j))
                {
                    for(int l = 0; l < m; l++)
                    {
                        if(grassHeight.at(i).at(j) < grassHeight.at(i).at(l))
                        {
                            nRet++;
                            i = n, j = m, k = n, l = m; // exit all 4 for loops.
                        }
                    }
                }
            }
        }
    }

    return arrRet.at(nRet);
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        cout << "Case #" << i + 1 << ": " << solve() << endl;
    }
    return 0;
}

t=int(input())
result=[]
for i in range(t):
    n,m = map(int,input().split(' '))
    input_d = [0 for ele in range(n)]
    for y in range(n):
        input_d[y] = input().split(' ')
    input_af = [0 for ele in range(n)]
    for y in range(n):
        _max = max(input_d[y])
        input_af[y] = [_max for i in range(m)]    
    for x in range(m):
        _temp1 = [input_d[y][x] for y in range(n)]
        _temp2 = [input_af[y][x] for y in range(n)]
        if _temp1 != _temp2:
            _min = min(_temp1)
            for y in range(n):
                input_af[y][x] = _min
    output='YES'
    for row in range(n):
        if input_d[row] != input_af[row]:
            output = 'No'
    result.append(output)
for i in range(t): 
    print('Case #{0}:{1}'.format(1+i,result[i]))