Квалификация 2019. Задача B

 

Задача в оригинале. Краткий перевод: есть "лабиринт" размером N на N клеток. Старт в северо-западном (левом верхнем) углу, цель - юго-восточный (правый нижний) угол. Ходить можно только вправо (ход 'E') и вниз (ход 'S'). Лидия уже прошла лабиринт. Надо найти свой путь, не повторяя ее ходов. Пути могут пересекаться.

Решение: зная путь Лидии, получаем свои первый и последний шаги. Если последний шаг 'S', идем максимально вправо, дойдя до стены, поворачиваем вниз. Если последний шаг 'E', то же самое проделываем с походом вниз и вправо. С Лидией можем оказаться в одной и той же клетке только на таком же по счету шаге. Отслеживаем свое текущее местоположение и положение Лидии. Если они совпали - выбираем ход, не совпадающий с ней, независимо от своего приоритетного направления.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {

    public static int x, y, lx, ly;

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = null;
        if (args.length > 0)
            br = new BufferedReader(new FileReader(args[0]));
        else
            br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int tt = 1; tt <= t; ++tt) {
            x = 1; y = 1; lx = 1; ly = 1;
            int n = Integer.parseInt(br.readLine());
            char[] lydia = br.readLine().toCharArray();
            int steps = lydia.length;

            char[] me = new char[steps];

            me[0] = (lydia[0] == 'E' ? 'S' : 'E');
            meStep(me[0]);
            lydiaStep(lydia[0]);
            me[steps - 1] = (lydia[steps - 1] == 'E' ? 'S' : 'E');

            for(int i = 1; i < steps-1; ++i){
                if(me[steps-1] == 'E'){
                    if(x != lx && y != ly){
                        if(y < n)
                            me[i] = 'S';
                        else
                            me[i] = 'E';
                    } else {
                        me[i] = (lydia[i] == 'E' ? 'S' : 'E');
                    }
                } else {
                    if(x != lx && y != ly){
                        if(x < n)
                            me[i] = 'E';
                        else
                            me[i] = 'S';
                    } else {
                        me[i] = (lydia[i] == 'E' ? 'S' : 'E');
                    }
                }
                meStep(me[i]);
                lydiaStep(lydia[i]);
            }

            System.out.println("Case #" + tt + ": " + String.valueOf(me));
        }
    }

    public static void meStep(char c){
        if (c == 'E')
            ++x;
        else
            ++y;
    }

    public static void lydiaStep(char c){
        if (c == 'E')
            ++lx;
        else
            ++ly;
    }
}

 

Published on May 23rd, 2019