专栏首页个人学习总结做题总结—— Latin Squares

做题总结—— Latin Squares

做题总结—— Latin Squares

原题

题意分析:

题目就是输入一个二维数组(用来表示矩阵),判断对于矩阵中的每一个数字是否在该数字所在的行、所在的列的只出现一次(相当于数独的概念)。如果是的话,则该矩阵是拉丁方,再判断矩阵的第一行、第一列的元素是否按照升序的方式排列的,从而进行对应的判断输出

做题思路:

  • 由于输入数据中含有字符,所以存储数据的二维数组需要使用char类型
  • 再输入二维数组以及这个矩阵的转置的转换成int型,字符进行对应的转换
  • 对于矩阵的每个数字分别记录该数字在其所在行、所在列出现的次数(利用数组下标)
  • 如果某个数字在所在行或者所在列出现次数>=2,则该矩阵不是拉丁方;如果全部数字在所在行、所在列出现次数<=1,该矩阵是拉丁方
  • 对于拉丁方再判断矩阵的第一行、第一列是否升序排列(用一个循环即可,如果后面的元素小于前面的元素则不是)

代码实现

#include<bits/stdc++.h>    //万能头文件
using namespace std;
int main()
{
    int n,i,j,num,num1,num2,flag=0;
    char a[50][50],b[50][50];
    int c[50][50],d[50][50],x[50][50],y[50][50];
    cin>>n;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cin>>a[i][j];
            b[j][i]=a[i][j];        //矩阵的转置
            if(a[i][j]>='0' && a[i][j]<='9')     //对应字符的转换
            {
                num1=a[i][j]-48;
            }
            else if(a[i][j]>='A' && a[i][j]<='Z')
            {
                num1=a[i][j]-55;
            }
            
            if(b[j][i]>='0' && b[j][i]<='9')
            {
                num2=b[j][i]-48;
            }
            else if(b[j][i]>='A' && b[j][i]<='Z')
            {
                num2=b[j][i]-55;
            }
            x[i][j]=num1,y[j][i]=num2;       //char类型转换为int类型
            c[i][num1]++;
            d[j][num2]++;
        }
    }
	//判断是否每个数字在其所在行、所在列只出现一次
    for(i=0;i<n;i++)
    {
        for(j=0;j<=35;j++)
        {
            if(c[i][j]>=2 || d[i][j]>=2)    //如果出现次数>=2,标志变量flag=1,表示该矩阵不是拉丁方
            {
                flag=1;
                break;
            }
        if(flag==1)
        {
            break;
        }               
    }
    //int f=0,cnt=0;
    if(flag==0)             //如果该矩阵是拉丁方,判断第一行、第一列的元素是否升序排列
    {
        for(i=1;i<n;i++)
        {
            if(x[0][i]<=x[0][i-1] || y[0][i]<=y[0][i-1])   //升序排列的判断过程
            {
                cout<<"Not Reduced"<<endl;
                break;
            }
            //cnt++;
        }
        if(i==n)
        {
            cout<<"Reduced"<<endl;
        }
        //cout<<"Yes"<<endl;

    }
    else
    {
        cout<<"No"<<endl;
    }
    //system("pause");
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python教程: Python 介绍

         -h                        Display this usage message

    py3study
  • 做题总结——Delayed Work

    这道题目是来计算最低的支付金额,该金额由工人的工资和罚款两部分组成。根据题意描述可知,工资的表达式:MX,罚款的表达式:(KP)/M,因此总金额表达式:MX+(...

    用户8224910
  • 做题总结——Pawn’s Revenge

    这道题目自己一开始时也没有思路(后来才发现其实也并不难,实在是学的不太好),后来从网上查找了一些资料,大概明白了这道题目的思路。这道题目是在已经有且只有一个K棋...

    用户8224910
  • 做题总结——Fear Factoring

    开始自己的做法是特别愚蠢的 暴力破解法,也就是分别枚举[a,b]区间里每一个数的因数,最后累加起来,可想而知这种做法肯定是不对的。后面听了学长的讲解,这道题一共...

    用户8224910
  • 做题总结——中位数

    这道题目题意其实并不理解,相当于在插入数据的过程中动态求中位数,每当插入奇数个数据时就求这所有奇数个数据的中位数。

    用户8224910
  • 做题总结——造房子

    用户8224910
  • 彻底摆脱乱码的困惑

    先给大家出个思考题吧,一个汉字占多少字节?是不是网上搜出的答案五花八门,那么读完本篇文章,我希望你至少可以准确知道这个问题的答案,我觉得就算是收获

    全栈程序员站长
  • 编码、R 与 Windows (一)

    本期大猫将开个新帖介绍R中的编码问题。就像导言中说的,编码是一个常常被忽视的“小问题”——直到他给你造成成吨的伤害Orz。它尤其频繁出现于数据传输中,例如你在澳...

    用户7652506
  • 做题总结——younik要排号

    这道题目理解起来不难,就相当于求younik之前有多少个不同的人,再加上一,就是younik是第几个被叫到的人。

    用户8224910
  • 做题总结——使徒袭来

    这道题目利用数学知识可以知道,当三个正整数的值相等时,三个数的和最小,相当于a=b=c=n^(1/3)时,(a+b+c) min=3*n ^(1/3),编写代码...

    用户8224910
  • 做题总结——虚空之力

    这道题目是求出一个字符串中能够挑选出对应字符从而组成指定字符串(“king” 或 “kinging”)的数量

    用户8224910
  • 做题总结——走出迷宫

    从起点开始,分别向上、下、左、右四个方向进行搜索,如果搜索到了终点,则说明能够到达终点;否则,将该点压入队列之中,继续进行下面的搜索,并将该点标记成已访问。

    用户8224910
  • 做题总结——数字三角形

    先介绍一种解法。这道题目可以利用“杨辉三角”的思路,根据一个上面的元素与下面两个元素的递推公式(在动态规划里面称作状态转移方程),从下至上地解决此问题(详细思路...

    用户8224910
  • 做题总结——牛牛爱博弈

    自己再网上看了一些题解,感觉还是没有弄明白这其中的原理,所以就不在这写了,关于数论中博弈原理的各种应用需要自己去进行学习,总之 结论就是当n%3==0时,则牛牛...

    用户8224910
  • 做题总结——小M和天平

    根据这道题给出的数据范围可以知道,利用所有的石头能够查询的物体质量是不会查过100*100=10000的,所以可以直接利用暴力枚举的方法进行求解。

    用户8224910
  • 做题总结——单词查找树

    这道题目就是一道Trie树相关操作的题目(这道题目只涉及了插入操作),求最少的结点数目就相当于输出向Trie树中插入的最后一个结点的序号(注意开始就有根结点)

    用户8224910
  • 大数据那些事(7):腾飞的拉丁猪

    2007到2008年的Hadoop世界,是Hadoop发展历史上非常关键的一年。这一年Yahoo Research 发表了Pig Latin的paper 在 S...

    用户1564362
  • 大数据那些事(7):腾飞的拉丁猪

    2007到2008年的Hadoop世界,是Hadoop发展历史上非常关键的一年。这一年Yahoo Research 发表了Pig Latin的paper 在 S...

    用户1564362
  • 专治 MySQL 乱码, 再也不想看到乱码了!

    MySQL出现乱码的原因有很多,一般与character_set参数有关。我们先来看看有哪些参数:

    Bug开发工程师

扫码关注云+社区

领取腾讯云代金券