Задача взята с сайта e-olymp
Условие
Движение робота управляется программой. Программа состоит из следующих команд:
- [latex]S[/latex] — сделать шаг вперед
- [latex]L[/latex] — повернуться на [latex]90°[/latex] влево
- [latex]R[/latex] — повернуться на [latex]90°[/latex]вправо
Напишите программу, которая по заданной программе для робота определит, сколько шагов он сделает прежде, чем впервые вернется на то место, на котором уже побывал до этого, либо установит, что этого не произойдет.
Входные данные
Одна строка из заглавных латинских букв [latex]S[/latex], [latex]L[/latex], [latex]R[/latex], описывающая программу для робота. Общее число команд в программе не превышает [latex]200[/latex], при этом команд [latex]S[/latex] — не более [latex]50[/latex].
Выходные данные
Выведите одно число, количество шагов, которое будет сделано (то есть выполнено команд [latex]S[/latex]) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите число [latex]-1[/latex].
Тесты
| № | Inputs | Outputs |
| 1 | SSLSLSLSSRSRS | 5 |
| 2 | LSSSS | -1 |
| 3 | LLSRSRSRSLLLLSSSSLRSRSSSRSRSRS | 15 |
| 4 | LLLLLLLL | -1 |
| 5 | SRLSRLSLRSLRLSLSLSLSSSLRLSSLRSLRSRSRSRSLRLSRLLLLLSRLSRL | 7 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <vector> using namespace std; struct point{ int x, y; point(){ x = 0; y = 0; } point(int x1,int y1){ x=x1; y=y1; } bool isequal(point&a, point&b); }my_point; bool point::isequal(point&a, point&b){ return a.x == b.x and a.y == b.y; } int main() { int counter = 0, x = 0, y = 0, res = 0; point a; char c; bool stop = false; vector coor(1); while(cin >> c and stop == false){ if(c == 'L'){ counter = (counter + 1)%4; } else if(c == 'R'){ counter = ((counter - 1) + 4)%4; } else{ if(counter == 0){ y++; } else if(counter == 1){ x--; } else if(counter == 2){ y--; } else{ x++; } res++; point a(x,y); for(int j = 1; j < coor.size();j++){ if(my_point.isequal(coor[j],a)){ stop = true; } } coor.push_back(a); } } cout << ((stop == true) ? res : -1); return 0; } |
Решение
Если представить, что точка старта движения робота имеет координаты [latex]\left(0;0 \right)[/latex], то, соответственно, при движении координата будет изменяться на 1 единицу за шаг. Всего координата может изменяться четырьмя способами: координата [latex]x[/latex] уменьшается на единицу, координата [latex]x[/latex] увеличивается на единицу, координата [latex]y[/latex] уменьшается на единицу, координата [latex]y[/latex] увеличивается на единицу. Тогда можно сделать вывод, что эти 4 состояния можно привязать к счетчику, который будет меняться при каждом повороте налево и направо. Для хранения координат как единого объекта можно создать структуру point. Также необходимо запоминать в массив координаты точки после передвижения вперед для того, чтобы в будущем проверять каждую точку на совпадение с предыдущими, чтобы знать когда прервать проверку строки. В главном цикле при встрече символа «[latex]S[/latex]» делаем проверку на состояние счетчика, чтобы увеличивать соответствующую координату. После изменения координаты необходимо проверить ее на совпадение с предыдущими, если она совпала, то назначаем переменной stop значение true для того, чтобы прервать цикл и вывести результат. Если координата не совпала, то добавляем ее в массив(если использовать vector, это делается с помощью команды push_back(), если обычный массив, то придется создать дополнительную переменную и увеличивать ее каждую встречу команды «[latex]S[/latex]»). Если в итоге робот не вернется в то место, где побывал, то переменная stop останется со значением false и выведется «[latex]-1[/latex]».
Зачем создавать два массива для разных координат, так как они несут смысл в парах, то наверно правильнее будет сделать структуру point и уже работать с одним массивом точек
Да, пожалуй так будет логичнее, спасибо за совет, исправил!
Запоминание всей строки сразу может быть несколько нерациональным с точки зрения памяти. Да, по условию задачи, где число символов не превышает 200 это не существенно, но всё же более практичным и изящным решением, мне кажется, было бы работать с потоком данных: считывать по символу и сразу обрабатывать их.
Спасибо за подсказку, хотя в условиях данной задачи особой разницы между методами не видно, но все же, действительно, так решение выглядит проще и нагляднее, исправил.