Задача про робот пылесос

Question

Задача про робот пылесос

sadsawd Ученик (60), на голосовании 6 дней назад

На очередном соревновании по робототехнике одна из команд показала робота-пахаря, который ходит по прямоугольному полю и вспахивает под собой поле. Но есть проблема – робот если по пути попадает в спаханное место, он в нём застревает.

Для тестирования команда решила провести следующий эксперимент: они решили, что пусть робот передвигается по прямоугольному полю размера N на M, которое разбито на клетки размером 1*1. В каждой клетке есть натуральные числа (время, которое требуется роботу, чтобы вспахать клетку). Также на поле расставлены метки-направления, которые обозначают, куда должен продвинуться робот дальше, после достижения клетки с меткой (на метку заехать нельзя, это как стена, на которой стоит указатель, куда двигаться дальше).

Ребята из команды попросили помочь им с написанием программы, которая по входному полю, числам в нём и меткам-направления, поможет понять, сможет ли робот выполнить свою работу и выехать за границы поля или он застрянет. На вход также подаётся точка входа робота на поле в виде координаты от 1 до M (робот заходит на поле всегда снизу).

Метки направления бывают четырёх видов, обозначающиеся цифрой от 1 до 4: (См. прикреп. фото)

Метка-направление работает как изменение маршрута, то есть, после вспахивания, робот идёт в том направлении, куда указывает метка. Но на саму метку робот заехать не может. (См. прикреп. фото)

Входные параметры

На первой строке подаются три целых числа N – количество строк на поле, M – количество столбцов на поле, K – точка входа робота (номер столбца, в которых робот въезжает с нижней части поля).

(1 <= N, M <= 10000, 1 <= K <= M).

Далее подаются на N строках по M натуральных чисел – сколько требуется времени, на вспахивание ячейки поля.

Далее подаётся целое число P (1 <= P <= N*M) – количество меток-направлений.

После на P строках подаются метки в виде (номер метки;номер строки; номер столбца), например, 1;2;3 – значит, что метка вида 1 расположена на второй строке, третьем столбце.

Выходные параметры:

Выведите на первой строке координаты, на которых застрянет робот, через пробел (сперва номер строки, затем столбца). Если робот не застрянет, выведите 0.

На второй строке выведите сумму единиц времени, которое робот проведёт на поле (сумма чисел в клетках).

Примечание:

робот считается застрявшим, если он попал в ячейку, которую посещал ранее (она уже была вспахана);
если робот выехал за пределы поля, то считается, что он не застрял;
если робот подъехал к метке, которое указывает на направление, по которому он приехал (ехал вверх и метка вверх, то он остаётся на этой клетке и считается, что робот застрял)

Входные данные
4 5 2
1 3 2 1 4
7 1 4 2 2
4 1 3 4 5
6 1 2 7 3
3
2;2;2
1;3;5
3;1;3
Выходные данные
0
12

Входные данные
4 5 2
1 3 2 1 4
7 1 4 2 2
4 1 3 4 5
6 1 2 7 3
4
2;3;2
1;4;5
4;1;4
3;2;2
Выходные данные
4 3
23

Answer 1

Джорно Джованни Мастер (1797) 1 месяц назад

слишком много читать

Answer 2

 def solve(): 
    n, m, k = map(int, input().split()) 
    field = [] 
    for _ in range(n): 
        field.append(list(map(int, input().split()))) 
    p = int(input()) 
    marks = {} 
    for _ in range(p): 
        mark_str = input().split(';') 
        marks[(int(mark_str[1]), int(mark_str[2]))] = int(mark_str[0]) 
 
    visited = set() 
    row, col = n - 1, k - 1 
    total_time = 0 
    prev_dir = None  
 
    while 0 <= row < n and 0 <= col < m: 
        if (row, col) in visited: 
            print(row + 1, col + 1) 
            print(total_time) 
            return 
 
        visited.add((row, col)) 
        total_time += field[row][col] 
         
        if (row, col) in marks: 
            mark_type = marks[(row,col)] 
             
            if mark_type == 1:  
                
                if prev_dir == 2: 
                   
                    print(row+1, col+1) 
                    print(total_time) 
                    return 
                else: 
                    prev_dir = 1 
                    row -= 1 
            elif mark_type == 2: 
                if prev_dir == 1: 
                    
                    print(row+1, col+1) 
                    print(total_time) 
                    return 
                else: 
                    prev_dir = 2 
                    row += 1 
            elif mark_type == 3: 
                if prev_dir == 4: 
                    print(row+1, col+1) 
                    print(total_time) 
                    return 
                else: 
                    prev_dir = 3 
                    col -= 1 
            elif mark_type == 4: 
                if prev_dir == 3: 
                    print(row+1, col+1) 
                    print(total_time) 
                    return 
                else: 
                    prev_dir = 4 
                    col += 1 
         
         
        else: 
             prev_dir = 1 
             row -= 1 
     
    print(0) 
    print(total_time) 
 
 
solve()