Stable Wall - Google Kickstart 2020 Round C Problem 2

Welcome to my blog !

Here is the link to the PROBLEM .

So , the question is easy-medium .

We are given a wall of letters and we need to find if its stable or not .

So , a wall would be stable , only if the letters can be placed without falling , like the letter to be placed should be the ground letter or the letter under it should be placed .

So , lets discuss the solution of this problem .

So we iterate over all the columns and then over all the rows from bottom to top in a nested life .

So , whatever the letter is there at the i,j position , we check if it is placed or not , if it is placed , we continue , else we check if all the letters of that kind can be placed with the constraints . If they can we place them , if they cant be placed then we skip that element and move  on .

We repeat this process 26 times , this is the max times this process should be repeated to place the letters.

if they still cant be placed , then they can never me placed . 

Every time a letter is placed , we push it into a vector . 

Here s the C++ code :-

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

int main()

{

    int t,T;

    std::cin>>t;

    T=t;

    while(t--)

    {

        vector<pair<int,int>> v[26];

        vector<pair<int,int>>::iterator it,it1;

        int r,c;

        std::cin>>r>>c;

        char arr[r][c];

        bool visited[r][c]={0};

        bool temp[r][c];

        int i=r-1,j=0;

        while(i>=0)

        {

            j=0;

            while(j!=c)

            {

                std::cin>>arr[i][j];

                v[(int)arr[i][j]-65].push_back(make_pair(i,j));

                visited[i][j]=0;

                

                j++;

            }

            i--;

        }

        i=0;

        while(i!=26)

        {

            sort(v[i].begin(),v[i].end());

            i++;

        }

        int ans=0;

        vector<char> order;

        vector<char>::iterator counter;

        i=0;

        j=0;

        int r1,c1,l,m;

        int flag;

        char current;

        i=0;

        while(i!=r)

        {

            j=0;

        while(j!=c)

        {

            flag=1;

            current=arr[i][j];

            if(visited[i][j]==1)

            {

                j++;

                continue;

            }

            it=v[(int)arr[i][j]-65].begin();

            while(it!=v[(int)arr[i][j]-65].end())

            {

               r1=it->first;

               c1=it->second;

               //std::cout<<r1<<" "<<c1<<" ";

               if(r1==0 || visited[r1-1][c1]==1)

                {

                    //std::cout<<"yes";

                    visited[r1][c1]=1;

                }

                else if(visited[r1][c1]==1)

                {

                   // std::cout<<"done";

                    flag=0;

                }

                else

                {

                    //std::cout<<"fall";

                    flag=0;

                     l=0;m=0;

                while(l!=r)

                {

                    m=0;

                    while(m!=c)

                    {

                        if(arr[l][m]==current)

                        {

                            visited[l][m]=0;

                        }

                        m++;

                    }

                    l++;

                }

                    break;

                }

                it++;

            }

            if(flag==0)

            {

               

            }

            else

            {

                order.push_back(current);

            }

            //std::cout<<flag<<" "<<current<<" ";

            j++;

        }

        i++;

        }

        

        if(order.size()==0)

        {

            std::cout<<-1<<std::endl;

        }

        else

        {

        counter=order.begin();

        while(counter!=order.end())

        {

            std::cout<<(*counter);

            counter++;

        }

        std::cout<<std::endl;

        }

    }

}

Please leave your doubts and queries in comments section .