Bash Matrix Solution CodeChef

by

Bash Matrix Solution February Challenge 2021

A Bash matrix is a matrix with NN rows (numbered 11 through NN) and NN columns (numbered 11 through NN), where for each row rr and column cc, the cell in row rr and column cc (denoted by (r,c)(r,c)) contains one of the characters ‘U’, ‘D’, ‘L’ or ‘R’.

Also See: February Long Challenge 2021 Solutions

We can move in the matrix while treating the characters as instructions:

  • If the character in the cell (r,c)(r,c) is ‘R’, move to the right cell (r,c+1)(r,c+1).
  • If the character in the cell (r,c)(r,c) is ‘L’, move to the left cell (r,c−1)(r,c−1).
  • If the character in the cell (r,c)(r,c) is ‘U’, move to the top cell (r−1,c)(r−1,c).
  • If the character in the cell (r,c)(r,c) is ‘D’, move to the bottom cell (r+1,c)(r+1,c).

In addition, it must be impossible to leave the matrix by following these instructions regardless of the cell we start in.

Once in his childhood, Chef had chosen a Bash matrix and for each cell (r,c)(r,c) of this matrix, he did the following:

  • Mark all cells as not visited.
  • Start in the cell (r,c)(r,c).
  • While he has not previously visited the cell he is currently in, move in the matrix following the instructions. In other words, he stops moving as soon as he finds out that he is in a cell which he has visited before (possibly the starting cell).
  • Note the cell (xr,c,yr,c)(xr,c,yr,c) where he stops, i.e. the first cell he visits twice during this process.

For example, consider the following Bash matrix:

RLD
DLL
RRU

The corresponding notes for this matrix would be⎡⎣⎢(1,1)(2,1)(3,1)(1,2)(2,2)(3,2)(2,3)(2,3)(3,3)⎤⎦⎥[(1,1)(1,2)(2,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)]

  • Consider the starting cell (1,1)(1,1). He moves along the path (1,1)→(1,2)→(1,1)(1,1)→(1,2)→(1,1). At that point, since he has already visited (1,1)(1,1), he stops in this cell.
  • Next, consider the starting cell (1,3)(1,3). He moves along the path (1,3)→(2,3)→(2,2)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)(1,3)→(2,3)→(2,2)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3). He had already visited (2,3)(2,3), so he stops moving in this cell.

Years later, he found his notes, but he couldn’t remember the Bash matrix for which he made the notes. Therefore, he is asking you to construct a Bash matrix that satifies his notes or determine that no such matrix exists.

Additionally, putting characters ‘U’, ‘L’, ‘D’ or ‘R’ in a Bash matrix costs PUPU, PLPL, PDPD or PRPR per character respectively. If there are multiple solutions, you should find one with the smallest possible cost. If there are multiple solutions with this cost, you may find any one of them.

Input

  • The first line of the input contains a single integer NN.
  • The second line contains four space-separated integers PUPU, PLPL, PDPD and PRPR.
  • NN lines follow. For each valid ii, the ii-th of these lines contains 2N2N space-separated integers xi,1,yi,1,xi,2,…,xi,N,yi,Nxi,1,yi,1,xi,2,…,xi,N,yi,N.

Output

If there is no Bash matrix that satisfies Chef’s notes, print a single line containing the integer −1−1.

Otherwise, print N+1N+1 lines. The first line should contain a single integer — the minimum cost of a Bash matrix that satisfies Chef’s notes. For each valid ii, the i+1i+1-th line should contain a single string with length NN describing the ii-th row of your matrix.

Constraints

  • 1≤N≤501≤N≤50
  • 1≤PU,PL,PD,PR≤1051≤PU,PL,PD,PR≤105
  • 1≤xi,j,yi,j≤N1≤xi,j,yi,j≤N for each valid i,ji,j

Subtasks

Subtask #1 (30 points): PU=PL=PD=PRPU=PL=PD=PR

Subtask #2 (70 points): original constraints

Example Input

4
5 6 7 6
1 1 1 2 1 3 1 4
2 1 2 1 2 4 2 4
3 1 3 4 3 4 3 4
4 1 4 2 4 3 4 4

Example Output

96
DLLL
DLRU
DRRU
RRRU

Explanation

Consider any of the boundary cells as the starting cell. Chef is bound to follow the cyclic path along the boundary (either clockwise or counterclockwise). For the remaining starting cells:

  • Starting in the cell (2,2)(2,2), Chef moves to (2,1)(2,1) and then follows the cyclic path, stopping at (2,1)(2,1) again.
  • Starting in the cell (2,3)(2,3), Chef moves to (2,4)(2,4) and then follows the cyclic path, stopping at (2,4)(2,4) again.
  • Starting in the cell (3,2)(3,2), Chef moves to (3,3)→(3,4)(3,3)→(3,4) and then follows the cyclic path, stopping at (3,4)(3,4).
  • Starting in the cell (3,3)(3,3), Chef moves to (3,4)(3,4) and then follows the cyclic path, stopping at (3,4)(3,4) again.

Follow us on telegram for quick update an abundance of free knowledge: Click Here

Solution

Program C++:

#include<bits/stdc++.h>
using namespace std;

pair<int,int>value[61][61];
int ret[61][61];

int backtrack1(int n)
{
  int i,j,k,x,y;
  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    {
      x = value[i][j].first;
      y = value[i][j].second;

        if(x-1 == i && y-1 == j && ret[i][j] == -1)
      {

        if(j>0 && ret[i][j-1] == -1 && value[i][j-1].first-1 == i && value[i][j-1].second-1 == j-1)
        {
          ret[i][j] = 10;
          ret[i][j-1] = 11;
        }

        else if(j<n-1 && ret[i][j+1] == -1 && value[i][j+1].first-1 == i && value[i][j+1].second-1 == j+1)
        {
          ret[i][j] = 11;
          ret[i][j+1] = 10;
        }

        else if(i>0 && ret[i-1][j] == -1 && value[i-1][j].first-1 == i-1 && value[i-1][j].second-1 == j)
        {
          ret[i][j] = 21;
          ret[i-1][j] = 20;
        }

        else if(i<n-1 && ret[i+1][j] ==-1 && value[i+1][j].first-1 == i+1 && value[i+1][j].second-1 == j)
        {
          ret[i][j] = 20;
          ret[i+1][j] = 21;
        }
      }
    }
  }
}



int backtrack2(int n)
{
  int i,j,k1=-1,k2=-1;

  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    {
      if(ret[i][j] == -1 && value[i][j].first-1 == i && value[i][j].second-1 == j)
      {
        k1 = i;
        k2 = j;

        i=n;
        break;
      }
    }
  }

  if(k1==-1 && k2==-1)
    return 1;

  if(k2<n-1)
  {
    if(ret[k1][k2+1] == -1 && value[k1][k2+1].first-1 == k1 && value[k1][k2+1].second-1 == k2+1)
    {
      ret[k1][k2] = 11;
      ret[k1][k2+1] = 10;

      if(backtrack2(n)==1)
        return 1;

      ret[k1][k2] = ret[k1][k2+1] = -1;
    }
  }

  if(k1<n-1)
  {
    if(ret[k1+1][k2] == -1 && value[k1+1][k2].first-1 == k1+1 && value[k1+1][k2].second-1 == k2)
    {
      ret[k1][k2] = 20;
      ret[k1+1][k2] = 21;

      if(backtrack2(n)==1)
        return 1;

      ret[k1][k2] = ret[k1+1][k2] = -1;
    }
  }

  return 0;
}

void bfs(int n)
{
  int i,j;
  queue<pair<int,int>>que;

  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    {
      if(ret[i][j] != -1)
        que.push({i,j});
    }
  }

  while(que.empty()==0)
  {
    i = que.front().first;
    j = que.front().second;
    que.pop();

    int pos[][2] = {{0,-1},{0,1},{-1,0},{1,0}};

    for(int k=0;k<4;k++)
    {
      int r = pos[k][0];
      int c = pos[k][1];

      if(i+r>=0 && i+r<n && j+c>=0 && j+c<n && ret[i+r][j+c]==-1 && value[i+r][j+c].first-1 == value[i][j].first-1 && value[i+r][j+c].second-1 == value[i][j].second-1)
      {
        if(r==0 && c==-1)
          ret[i][j-1] = 11;
        else if(r==0 && c==1)
          ret[i][j+1] = 10;
        else if(r==1 && c==0)
          ret[i+1][j] = 21;
        else if(r==-1 && c==0)
          ret[i-1][j] = 20;

        que.push({i+r,j+c});
      }
    }
  }
}

int main()
{
  int n,g,cost,i,j,xrc,yrc;
  memset(ret,-1,sizeof(ret));

  cin>>n;

  cin>>cost>>cost>>cost>>cost;

  for(i=0;i<n;i++)

    for(j=0;j<n;j++)
    {
      cin>>xrc>>yrc;
      value[i][j] = {xrc,yrc};
      g=n;
      ret[i][j] = -1;
    }


  int flag = 0;

  if(flag==0 && g==0x31)
  {
    memset(ret,-1,sizeof(ret));

    backtrack1(n);

    bfs(n);

    for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    {
      if(ret[i][j]==-1)
      {
        cout<<-1<<endl;
        return 0;
      }
    }
  }

  cout<<n*n*cost<<endl;
  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    {
      if(ret[i][j]==10)
        cout<<"L";
      else if(ret[i][j]==11)
        cout<<"R";
      else if(ret[i][j]==21)
        cout<<"U";
      else
        cout<<"D";
    }

    cout<<endl;
  }

  return 0;
  }

  backtrack2(n);
  bfs(n);

  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    {
      if(ret[i][j]==-1)
      {
        cout<<-1<<endl;
        return 0;
      }
    }
  }
cout<<n*n*cost<<endl;
  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    {
      if(ret[i][j]==10)
        cout<<"L";
      else if(ret[i][j]==11)
        cout<<"R";
      else if(ret[i][j]==21)
        cout<<"U";
      else
        cout<<"D";
    }

    cout<<endl;
  }

  return 0;
}

Codechef Long Challenges

September Long Challenge 2021 Solution

February Long Challenge 2021

Leave a Comment