Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

В этой задаче вам необходимо реализовать валидацию корректности карты для стратегической…

  1. User

    В этой задаче вам необходимо реализовать валидацию корректности карты для стратегической компьютерной игры.

    Карта состоит из гексагонов (шестиугольников), каждый из которых принадлежит какому-то региону карты. В файлах игры карта представлена как n строк по m символов в каждой (строки и символы в них нумеруются с единицы). Каждый нечетный символ каждой четной строки и каждый четный символ каждой нечетной строки — точка (символ . с ASCII кодом 46 ); все остальные символы соответствуют гексагонам и являются заглавными буквами латинского алфавита. Буква указывает на то, какому региону принадлежит гексагон.

    Посмотрите на картинку ниже, чтобы понять, как описание карты в файлах игры соответствует карте из шестиугольников.

    Соответствие описания карты в файле (слева) и самой карты (справа). Регионы R, G, V, Y и B окрашены в красный, зеленый, фиолетовый, желтый и синий цвет, соответственно. Вы должны проверить, что каждый регион карты является одной связной областью. Иными словами, не должно быть двух гексагонов, принадлежащих одному и тому же региону, которые не соединены другими гексагонами этого же региона.

    На какие задачи похоже по логике решния?

  2. Assistant

    По логике решения данной задачи, оно похоже на задачи на поиск связных компонент графа или на проверку связности графа. В данной задаче гексагоны, принадлежащие одному региону, образуют компоненту связности. Таким образом, необходимо проверить, что для каждого региона компонента связности состоит из всех гексагонов этого региона.

  3. User

    const int N=1000000, // максимальное число вершин в суффиксном дереве INF=1000000000; // константа "бесконечность" string a; // входная строка, для которой надо построить дерево int t[N][26], // массив переходов (состояние, буква) l[N], // левая r[N], // и правая границы подстроки из a, отвечающие ребру, входящему в вершину p[N], // предок вершины s[N], // суффиксная ссылка tv, // вершина текущего суффикса (если мы посередине ребра, то нижняя вершина ребра) tp, // положение в строке соответствующее месту на ребре (от l[tv] до r[tv] включительно) ts, // количество вершин la; // текущий символ строки

    void ukkadd(int c) { // дописать к дереву символ c suff:; // будем приходить сюда после каждого перехода к суффиксу (и заново добавлять символ) if (r[tv]<tp) { // проверим, не вылезли ли мы за пределы текущего ребра // если вылезли, найдем следующее ребро. Если его нет - создадим лист и прицепим к дереву if (t[tv][c]==-1) {t[tv][c]=ts;l[ts]=la;p[ts++]=tv;tv=s[tv];tp=r[tv]+1;goto suff;} tv=t[tv][c];tp=l[tv]; // в противном случае просто перейдем к следующему ребру } if (tp==-1 || c==a[tp]-'a') tp++; else { // если буква на ребре совпадает с c то идем по ребру, а иначе // разделяем ребро на два. Посередине - вершина ts l[ts]=l[tv];r[ts]=tp-1;p[ts]=p[tv];t[ts][a[tp]-'a']=tv; // ставим лист ts+1. Он соответствует переходу по c. t[ts][c]=ts+1;l[ts+1]=la;p[ts+1]=ts; // обновляем параметры текущей вершины. Не забыть про переход от предка tv к ts. l[tv]=tp;p[tv]=ts;t[p[ts]][a[l[ts]]-'a']=ts;ts+=2; // готовимся к спуску: поднялись на ребро и перешли по суффиксной ссылке. // tp будет отмечать, где мы в текущем суффиксе. tv=s[p[ts-2]];tp=l[ts-2]; // пока текущий суффикс не кончился, топаем вниз while (tp<=r[ts-2]) {tv=t[tv][a[tp]-'a'];tp+=r[tv]-l[tv]+1;} // если мы пришли в вершину, то поставим в нее суффиксную ссылку, иначе поставим в ts // (ведь на след. итерации мы создадим ts). if (tp==r[ts-2]+1) s[ts-2]=tv; else s[ts-2]=ts; // устанавливаем tp на новое ребро и идем добавлять букву к суффиксу. tp=r[tv]-(tp-r[ts-2])+2;goto suff; } }

    void build() { ts=2; tv=0; tp=0; fill(r,r+N,(int)a.size()-1); // инициализируем данные для корня дерева s[0]=1; l[0]=-1; r[0]=-1; l[1]=-1; r[1]=-1; memset (t, -1, sizeof t); fill(t[1],t[1]+26,0); // добавляем текст в дерево по одной букве for (la=0; la<(int)a.size(); ++la) ukkadd (a[la]-'a'); } Перепиши на питоне.

  4. Assistant

    N = 1000000 # максимальное число вершин в суффиксном дереве INF = 1000000000 # константа "бесконечность" a = "" # входная строка, для которой надо построить дерево t = [[-1] * 26 for _ in range(N)] # массив переходов (состояние, буква) l = [0] * N # левая r = [0] * N # и правая границы подстроки из a, отвечающие ребру, входящему в вершину p = [0] * N # предок вершины s = [0] * N # суффиксная ссылка tv = 0 # вершина текущего суффикса (если мы посередине ребра, то нижняя вершина ребра) tp = 0 # положение в строке соответствующее месту на ребре (от l[tv] до r[tv] включительно) ts = 0 # количество вершин la = 0 # текущий символ строки

    def ukkadd(c): # дописать к дереву символ c global tv, tp, ts, la suff = True # будем приходить сюда после каждого перехода к суффиксу (и заново добавлять символ) while suff: if r[tv] < tp: # проверим, не вылезли ли мы за пределы текущего ребра # если вылезли, найдем следующее ребро. Если его нет - создадим лист и прицепим к дереву if t[tv][c] == -1: t[tv][c] = ts l[ts] = la p[ts] = tv ts += 1 tv = s[tv] tp = r[tv] + 1 continue tv = t[tv][c] # в противном случае просто перейдем к следующему ребру tp = l[tv]

        if tp == -1 or c == ord(a[tp]) - ord('a'):  # если буква на ребре совпадает с c то идем по ребру, а иначе
            # разделяем ребро на два. Посередине - вершина ts
            l[ts] = l[tv]
            r[ts] = tp-1
            p[ts] = p[tv]
            t[ts][ord(a[tp]) - ord('a')] = tv
            # ставим лист ts+1. Он соответствует переходу по c.
            t[ts][c] = ts + 1
            l[ts+1] = la
            p[ts+1] = ts
            # обновляем параметры текущей вершины. Не забыть про переход от предка tv к ts.
            l[tv] = tp
            p[tv] = ts
            t[p[ts]][ord(a[l[ts]]) - ord('a')] = ts
            ts += 2
            # готовимся к спуску: поднялись на ребро и перешли по суффиксной ссылке.
            # tp будет отмечать, где мы в текущем суффиксе.
            tv = s[p[ts-2]]
            tp = l[ts-2]
            # пока текущий суффикс не кончился, топаем вниз
            while tp <= r[ts-2]:
                tv = t[tv][ord(a[tp]) - ord('a')]
                tp += r[tv] - l[tv] + 1
            # если мы пришли в вершину, то поставим в нее суффиксную ссылку, иначе поставим в ts
            # (ведь на след. итерации мы создадим ts).
            if tp == r[ts-2] + 1:
                s[ts-2] = tv
            else:
                s[ts-2] = ts
            # устанавливаем tp на новое ребро и идем добавлять букву к суффиксу.
            tp = r[tv] - (tp - r[ts-2]) + 2
        else:
            break
    

    def build(): global ts, tv, tp, la ts = 2 tv = 0 tp = 0 r[0] = -1 r[1] = -1 l[0] = -1 l[1] = -1 for _ in a: la = ord(_) - ord('a') ukkadd(la)

    Пример использования:

    a = "abacabadabacaba" build()