Question Name:GRID CHALLENGE

#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <iterator>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

void solve(){
	int n; cin >> n;
	vector<string> v(n);
	FOR(i, n) cin >> v[i];
	FOR(i, n) sort(v[i].begin(), v[i].end());
	bool b = true;
	FOR(i, n){
		string x;
		FOR(j, n) x.push_back(v[j][i]);
		string y = x;
		sort(y.begin(), y.end());
		if (x != y) {
			b = false;
		}
	}
	puts(b ? "YES" : "NO");
}

int main(){
	int t; cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}
  • Problem Description
    Given a squared sized grid G of size N in which each cell has a lowercase letter. Denote the character in the ith row and in the jth column as G[i][j].

    You can perform one operation as many times as you like: Swap two column adjacent characters in the same row G[i][j] and G[i][j+1] for all valid i,j.

    Is it possible to rearrange the grid such that the following condition is true?
    G[i][1]<=G[i][2]<=…<=G[i][N] for 1<=i<=N and 

    G[1][j]<=G[2][j]<=…<=G[N][j] for 1<=j<=N

    In other words, is it possible to rearrange the grid such that every row and every column is lexicographically sorted?

    Note:c1<=c2 , if letter c1 is equal to c2 or is before c2 in the alphabet.

    Input Format

    The first line begins with T, the number of testcases. In each testcase you will be given N. The following N lines contain N lowercase english alphabet each, describing the grid.

    Constraints
    1<=T<=100 
    1<=N<=100 

    Gij will be a lower case letter

    Output Format

    Print T lines. On the ith line print YES if it is possible to rearrange the grid in the ith testcase or NO otherwise.
  • Test Case 1
    Input (stdin)1
    5
    ebacd
    fghij
    olmkn
    trpqs
    xywuv
    Expected OutputYES
  • Test Case 2
    Input (stdin)1
    3
    fghij
    ebacd
    olmkn
    Expected OutputNO

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.