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
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
#include <iostream>
#include <vector>
#include <string>
# include <algorithm>

using namespace std;

vector<string> WczytajPlansze(int n)
{
    vector<string> plansza;
    for (int ii=0; ii<n; ii++)
    {
        string s;
        cin>>s;
        plansza.push_back(s);
    }
    return plansza;
}

bool czyPion(char c)
{
    if (c=='G' || c=='D')
        return true;
    else
        return false;
}

bool czyPoziom(char c)
{
    if (c=='L' || c=='P')
        return true;
    else
        return false;
}


class stanGry
{
public:
    char pion, poziom;
    stanGry():pion('?'),poziom('?'){};
    void zmienStan(char c){
        if (czyPion(c))
            pion=c;
        else if (czyPoziom(c))
            poziom=c;
    }
    int jakiSkret(char ruch);
    bool czyOkreslony(){
        if (pion!='?' && poziom!='?')
            return true;
        else
            return false;
    }
};

int stanGry::jakiSkret(char ruch)
{
    if(!czyOkreslony())
        return 0;
    if(czyPion(ruch))
    {
        if (ruch==pion || poziom=='?')
            return 0; // brak zmiany stanu, brak skretu
        else if ((poziom=='L' && ruch=='G') || (poziom=='P' && ruch=='D'))
            return 1; // skret w prawo
        else
            return -1; // skret w lewo
    }
    else // c -poziome
    {
        if (ruch==poziom || pion=='?')
            return 0; // brak zmiany stanu, brak skretu
        else if ((pion=='G' && ruch=='P') || (pion=='D' && ruch=='L'))
            return 1; // skret w prawo
        else
            return -1; // skret w lewo
    }
}

int liczSkrety(const string& ruchy, stanGry stan)
// policz sume netto skretow w prawo we wszystkich ruchach
{
    int sumaSkretow = 0;
    for (uint32_t ii=0; ii<ruchy.size(); ii++)
    {
        char c = ruchy[ii];
        sumaSkretow += stan.jakiSkret(c);
        stan.zmienStan(c);
    }
    return sumaSkretow;
}

template <class V>
void ruchLewo(vector<V>& plansza, int puste='.')
{
    int n=plansza.size(), m=plansza[0].size();
    for (int row=0; row<n; row++)
    {
        int jjr=0, jjw=0; // index to read and write
        while (jjr<m)
        {
            while(jjr<m && plansza[row][jjr]==puste)
                jjr++;
            if (jjr>=m)
                break;
            if (jjr!=jjw)
                swap(plansza[row][jjr], plansza[row][jjw]);
            jjw++;
            jjr++;
        }
    }
}

template <class V>
void ruchPrawo(vector<V>& plansza, int puste='.')
{
    int n=plansza.size(), m=plansza[0].size();
    for (int row=0; row<n; row++)
    {
        int jjr=m-1, jjw=m-1; // index to read and write
        while (jjr>=0)
        {
            while(jjr>=0 && plansza[row][jjr]==puste)
                jjr--;
            if (jjr<0)
                break;
            if (jjr!=jjw)
                swap(plansza[row][jjr], plansza[row][jjw]);
            jjw--;
            jjr--;
        }
    }
}

template <class V>
void ruchGora(vector<V>& plansza, int puste='.')
{
    int n=plansza.size(), m=plansza[0].size();
    for (int col=0; col<m; col++)
    {
        int iir=0, iiw=0; // index to read and write
        while (iir<n)
        {
            while(iir<n && plansza[iir][col]==puste)
                iir++;
            if (iir>=n)
                break;
            if (iir!=iiw)
                swap(plansza[iir][col], plansza[iiw][col]);
            iiw++;
            iir++;
        }
    }
}

template <class V>
void ruchDol(vector<V>& plansza, int puste='.')
{
    int n=plansza.size(), m=plansza[0].size();
    for (int col=0; col<m; col++)
    {
        int iir=n-1, iiw=n-1; // index to read and write
        while (iir>=0)
        {
            while(iir>=0 && plansza[iir][col]==puste)
                iir--;
            if (iir<0)
                break;
            if (iir!=iiw)
                swap(plansza[iir][col], plansza[iiw][col]);
            iiw--;
            iir--;
        }
    }
}

template <class V>
void ruchPlanszy(vector<V>& plansza, char kierunek, int puste='.')
{
    switch (kierunek) {
    case 'L':
        ruchLewo(plansza, puste);
        break;
    case 'P':
        ruchPrawo(plansza, puste);
        break;
    case 'G':
        ruchGora(plansza, puste);
        break;
    case 'D':
        ruchDol(plansza, puste);
        break;
    }
}

stanGry stanPoczatkowy(vector<string>& plansza, string& ruchy)
// okresl startowy naroznik
{
    // znajdz pierwszy ruch w pionie i poziomie lub tylko 1 jesli wszystkie ruchy sa w 1 plaszczyznie
    string ruchPocz="";
    uint32_t ii=1;
    while(ii<ruchy.size() && czyPion(ruchy[ii])==czyPion(ruchy[0]))
        ii++;
    ruchPocz+=ruchy[ii-1];
    if (ii<ruchy.size())
    {
        uint32_t poprz_ii=ii;
        while(ii<ruchy.size() && czyPion(ruchy[ii])==czyPion(ruchy[poprz_ii]))
            ii++;
        ruchPocz+=ruchy[ii-1];
    }
    ruchy = ruchy.substr(ii);

    // obroc plansze do poczatkowego naroznika i ustaw stan
    stanGry stan;
    for (uint8_t jj=0; jj<ruchPocz.size(); jj++)
    {
        ruchPlanszy(plansza, ruchPocz[jj]);
        stan.zmienStan(ruchPocz[jj]);
    }
    return stan;
}

template <class V>
void obrotWPrawo(vector<V>& plansza, const stanGry& stan, int ileRuchow=4, int puste='.') // 4 ruchy = pelny obrot
{
    string seq = "PDLG";
    int start = 0; // dla GL
    if(stan.pion=='G' && stan.poziom=='P')
        start = 1;
    else if(stan.pion=='D' && stan.poziom=='P')
        start = 2;
    else if(stan.pion=='D' && stan.poziom=='L')
        start = 3;
    for (int ii=0; ii<ileRuchow; ii++)
    {
        char ruch = seq[(ii + start)%4];
        ruchPlanszy(plansza, ruch, puste);
    }
}

template <class V>
void obrotWLewo(vector<V>& plansza, const stanGry& stan, int ileRuchow=4, int puste='.') // 4 ruchy = pelny obrot
{
    string seq = "DPGL";
    int start = 0; // dla GL
    if(stan.pion=='G' && stan.poziom=='P')
        start = 1;
    else if(stan.pion=='D' && stan.poziom=='P')
        start = 2;
    else if(stan.pion=='D' && stan.poziom=='L')
        start = 3;
    for (int ii=0; ii<ileRuchow; ii++)
    {
        char ruch = seq[(ii + start)%4];
        ruchPlanszy(plansza, ruch, puste);
    }
}

vector<int> znajdzPermutacje(const vector<string>& plansza, const stanGry& stan)
// zwraca permutacje elementow planszy przy pelnym obrocie
{
    int n=plansza.size(), m=plansza[0].size();
    //    vector<string> planszaNum(plansza);
    vector<vector<int>> planszaNum(n, vector<int>(m,-1));
    for (int ii=0; ii<n; ii++)
        for (int jj=0; jj<m; jj++)
        {
            if (plansza[ii][jj] != '.')
                planszaNum[ii][jj] = ii*m+jj;
        }
    obrotWPrawo(planszaNum, stan, 4, -1);

    vector<int> permutacja;
    for (int ii=0; ii<n; ii++)
        for (int jj=0; jj<m; jj++)
        {
            if (planszaNum[ii][jj] ==-1)
                permutacja.push_back(ii*m+jj);
            else
                permutacja.push_back(planszaNum[ii][jj]);
        }
    return permutacja;
}

void permutacjaPlanszy(vector<string>& plansza, const vector<int>& permut)
{
    vector<string> plansza_pocz(plansza);
    int n=plansza.size(), m=plansza[0].size();
    for (int ii=0; ii<n; ii++)
        for (int jj=0; jj<m; jj++)
        {
            int ind = permut[ii*m+jj];
            plansza[ii][jj] = plansza_pocz[ind/m][ind %m];
        }
}




//////////////////////////////////////////////
int main()
{
    int n, m, k;
    cin>>n>>m;
    vector<string> plansza = WczytajPlansze(n);

    // wczytaj ruchy
    cin>>k;
    string ruchy;
    cin>>ruchy;

    // ustaw stan poczatkowy - startowy nazoznik;
    stanGry stanPocz = stanPoczatkowy(plansza, ruchy);
    // stan pocz. jest stanem koncowym jesli wszystkie ruchy odbywaja sie
    // w 1 plaszczyznie (wtedy stanPocz jest nieokreslony)
    if (!stanPocz.czyOkreslony())
    {
        for (int ii=0; ii<n; ii++)
            cout<<plansza[ii]<<endl;
        return 0;
    }

    // policz skrety w prawo
    int skrety = liczSkrety(ruchy, stanPocz);
    //int obroty = skrety/4;

    // znajdz permutacje elementow przy pelnym obrocie
    vector<int> permut = znajdzPermutacje(plansza, stanPocz);

    // podziel permutacje na cykle i oblicz permutacje koncowa
    vector<int> permutKon(permut.size(), -1);
    vector<bool> odwiedzone(permut.size(), false);
    for(int ii=0; ii<(int)permut.size(); ii++)
    {
        if (odwiedzone[ii]==false)
        {
            // znajdz cykl w permutacji
            vector<int> cykl;
            int start_ind = ii, ind=start_ind;
            do
            {
                cykl.push_back(ind);
                odwiedzone[ind] = true;
                ind = permut[ind];
            } while(ind != start_ind);

            // odwroc cykl zeby dostac cykl obracajacy plansze a nie cofajacy obrot
            // reverse(cykl.begin(), cykl.end());

            // przepermutuj cykl do ostatniego pelnego obrotu przed stanem koncowym planszy
            int obroty =  (skrety/4) %(int)cykl.size();
            for(int jj=0; jj<(int)cykl.size(); jj++)
                permutKon[cykl[jj]] = cykl[(jj+obroty + cykl.size()) %cykl.size()];
        }
    }

    // przepermutuj elementy planszy
    permutacjaPlanszy(plansza, permutKon);

    // wykonaj brakujaca czesc niepelnego obrotu
    int ile = skrety %4;
    if (ile>0)
        obrotWPrawo(plansza, stanPocz,ile);
    else if (ile<0)
        obrotWLewo(plansza, stanPocz, -ile);


    for (int ii=0; ii<n; ii++)
        cout<<plansza[ii]<<endl;

    return 0;
}