DMOJ · nccc1j4s2

A Square Problem

This C++ solution uses simulation for DMOJ nccc1j4s2 A Square Problem. Read the reasoning, inspect the code, or try your own test case below.

nccc1j4s2Data structuresSimulationC++59 lines
Solution005of 248
Open official problem ↗ Download C++ file ↓ Search the library → Open full Code Lab ↗ Report an issue ↗

Approach

Simulation

A Square Problem matches classifying a square as No, Latin, or Reduced from its symbols and first row/column.

Data structures

Problem and code

Useful links.

Written by benbenyaojifen. Try the problem first, then compare your approach with the code.

Open official problem ↗View exact source file ↗
Implementation

a_square_problem.cpp

C++

    #include <bits/stdc++.h>
    using namespace std;
    int main(){
        ios::sync_with_stdio(0); cin.tie(0);
        int n; cin >> n;
        vector<vector<int>> v(n, vector<int>(n));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                char c; cin >> c;
                int val;
                if(c <= 'Z' && c >= 'A'){
                    val = int(c);
                } else {
                    val = c - '0';
                }
                v[i][j]= val;
            }
        }
        bool latin = true;
        for(int i = 0; i < n; i++){
            unordered_set<int> vis;
            for(int j = 0; j < n; j++){
                if(vis.count(v[i][j])){
                    latin = 0; break;
                }
                vis.insert(v[i][j]);
            }
        }
        for(int i = 0; i < n; i++){
            unordered_set<int> vis;
            for(int j = 0; j < n; j++){
                if(vis.count(v[j][i])){
                    latin = 0; break;
                }
                vis.insert(v[j][i]);
            }
        }
        if(latin){
            bool reduced = true;
            for(int i = 1; i < n; i++){
                if(v[0][i] < v[0][i - 1]){
                    reduced = false; break;
                }
            }
            for(int i = 1; i < n; i++){
                if(v[i][0] < v[i - 1][0]){
                    reduced = false; break;
                }
            }
            if(reduced){
                cout << "Reduced" << '\n';
            } else {
                cout << "Latin" << '\n';
            }
        } else {
            cout << "No" << '\n';
        }
        return 0;
    }
        

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗Keep studying →

Test this problem

Run your code here.

Paste your code, run a test case, compare the output, or trace selected values.

Full trace, comparison & stress testing ↗
StatusReady
Output
No run yet.
Diagnostics
No diagnostics yet.

Each run is isolated and has strict limits. Passing one test does not guarantee the judge will accept the solution.