Minimal Swap

You are given an N x N matrix. The chips are represented by B and R. You can swap any two adjacent rows of the matrix. Your goal is to have all the black chips in the matrix below or on the main diagonal.

Input

The first line of input gives the number of cases. The first line of each test case has one integer, N. Each of the next N lines contains N characters. Each character is either R or B.

 

Output 

For each input case print the minimum number of row swaps needed to have all the black chips in the matrix below or on the main diagonal.

 

Sample Input 

2

2

BR

BB

3

RRB

BRR

RBR

 

Sample Output 

0

2

 

using System;

using System.Collections.Generic;

using System.Text;

 

namespace MinimalSwap

{

    class MinimalSwap

    {

        static void Main(string[] args)

        {

            try

            {

                Console.Write("Enter number of rows: ");

                int N = int.Parse(Console.ReadLine());

                char[,] chipMatrix = new char[N, N];

                int[] pointer = new int[N];

                int counter = 0;

                for (int i = 0; i < N; i++)

                {

                    for (int j = 0; j < N; j++)

                    {

                        Console.Write("Enter element (" + (i + 1) + "," + (j + 1) + "): ");

                        chipMatrix[i, j] = char.Parse(Console.ReadLine());

                        if (chipMatrix[i, j] == ‘B’)

                        {

                            pointer[i] = j;

                        }

                    }

                }

                Display(chipMatrix);

 

                //Bubble sorting the pointer array and counting number of swaps

                for (int i = 1; i < N; i++)

                {

                    for (int j = 0; j < N – i; j++)

                    {

                        if (pointer[j] > pointer[j + 1])

                        {

                            int temp = pointer[j];

                            pointer[j] = pointer[j + 1];

                            pointer[j + 1] = temp;

                            counter++;

                        }

                    }

                }

                Console.WriteLine("Minimal number of swaps needed = " + counter);

            }

            catch (Exception e)

            {

                Console.WriteLine(e.Message);

            }

        }

 

        //Matrix Display

        public static void Display(char[,] tempMatrix)

        {

            int rows = tempMatrix.GetLength(0);

            int cols = tempMatrix.GetLength(1);

            Console.WriteLine("Displaying chip matrix:");

            Console.WriteLine("=======================");

            for (int i = 0; i < rows; i++)

            {

                for (int j = 0; j < cols; j++)

                {

                    Console.Write(tempMatrix[i, j]);

                    Console.Write(" ");

                }

                Console.WriteLine();

            }

            Console.WriteLine("=======================");

        }

    }

}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s