蓝桥杯 递增序列_蓝桥杯递增序列

题目：题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 4545 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。

例如，如下矩阵中
LANN
QIAO
有$LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN# 等 $13$ 个 递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看 是不同的顺序。
对于下面的 30 行 50 列的矩阵，请问总共有多少个递增序列？
（因序列太长就不给出了，具体请参照题目)
题目链接：https://www.lanqiao.cn/problems/819/learning/

思路：因为给出的数据不多，我们可以直接暴力n²m²求解完成题目
那么问题来了如何暴力？
同行同列的情况相信比较好处理
建四重循环后直接看列相等的时候看第二个字母行是否大于第一个字母的行比较后进行字母比较即可
列同理
问题还是同一方向45°的问题
这说明是要找对角线的字母进行比较
那么我们可以利用y1+x1x2+y2的方式表示一个斜对角线（左上到右下的对角线）
y1-x1y2-x2的方式表示另一个斜对角线
这样就完成了坐标比较的问题
但是还有一个问题，题目要求从左往右或者从上往下进行比较
这时候可以利用坐标看y1<=y2或x1<=x2的时候才进行比较
这样题目就完成啦
代码：

#include <iostream>

using namespace std;
char s[100][100];
int main()
{
    int a,b;
    cin>>a>>b;
    int ans=0;
    for(int i=0;i<a;i++)
        for(int k=0;k<b;k++)cin>>s[i][k];
    for(int i=0;i<a;i++){
        for(int k=0;k<b;k++){
            for(int j=0;j<a;j++){
                for(int m=0;m<b;m++){
                    if(m>=k||j>=i){//从左往右或者从上往下看
                    if(j>i&&m==k&&s[i][k]<s[j][m]){//同一列的情况
                            ans++;
                    }
                    else if(m>k&&j==i&&s[i][k]<s[j][m]){//同一行的情况
                            ans++;
                    }else if(m-j==k-i&&s[i][k]<s[j][m]){//正对角线
                            ans++;
                    }else if(m+j==k+i&&s[i][k]<s[j][m]){//斜对角线
                            ans++;
                    }
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35