首页 > 试题广场 >

游游的you矩阵

[编程题]游游的you矩阵
  • 热度指数：462 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
游游拿到了一个字符矩阵，她想知道有多少个三角形满足以下条件：
1. 三角形的三个顶点分别是 y、o、u 字符。
2. 三角形为直角三角形，且两个直角边一个为水平、另一个为垂直。

输入描述:
第一行输入两个正整数n,m，用空格隔开，代表矩阵的行数和列数。
接下来的n行，每行输入一个长度为m的字符串，代表游游拿到的矩阵。
1\leq n,m \leq 1000


输出描述:
输出一个整数，代表满足条件的三角形个数。
示例1

输入

2 3
you
our

输出

3

说明

如下图
算法知识视频讲解
添加回答
月有残头像 月有残
楼上的Python版本~ 
DEBUG = False

def num_of_trigle(matrix, rows, cols):
    # 初始化行和列计数器
    row_num = [[0, 0, 0] for _ in range(rows)]
    col_num = [[0, 0, 0] for _ in range(cols)]

    # 统计每个字符在每一行和每一列中的数量
    for i in range(rows):
        for j in range(cols):
            char = matrix[i][j]
            if char == 'y':
                row_num[i][0] += 1
                col_num[j][0] += 1
            elif char == 'o':
                row_num[i][1] += 1
                col_num[j][1] += 1
            elif char == 'u':
                row_num[i][2] += 1
                col_num[j][2] += 1

    # 计算直角三角形的数量
    num = 0
    for i in range(rows):
        for j in range(cols):
            char = matrix[i][j]
            if char == 'y':
                row_num_o = row_num[i][1]
                row_num_u = row_num[i][2]
                col_num_o = col_num[j][1]
                col_num_u = col_num[j][2]
                num += row_num_o * col_num_u + row_num_u * col_num_o
            elif char == 'o':
                row_num_y = row_num[i][0]
                row_num_u = row_num[i][2]
                col_num_y = col_num[j][0]
                col_num_u = col_num[j][2]
                num += row_num_y * col_num_u + row_num_u * col_num_y
            elif char == 'u':
                row_num_y = row_num[i][0]
                row_num_o = row_num[i][1]
                col_num_y = col_num[j][0]
                col_num_o = col_num[j][1]
                num += row_num_y * col_num_o + row_num_o * col_num_y

    return num

n, m = map(int, input().split())
matrix = []
for i in range(n):
    matrix.append([char for char in input()])
if DEBUG:
    print(matrix)
    print(len(matrix), len(matrix[0]))

res = num_of_trigle(matrix, n, m)
print(res)


发表于 2024-10-04 14:59:54 回复(0)
OneNiP头像 OneNiP
#include <bits/stdc++.h>
using namespace std;

typedef long long int64 ;

void print(vector<vector<char>> tu){
    int m=tu.size(),n=tu[0].size();
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cout<<tu[i][j]<<' ';
        }
        cout<<endl;
    }
}

void print(vector<vector<int>> tu){
    int m=tu.size(),n=tu[0].size();
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cout<<tu[i][j]<<' ';
        }
        cout<<endl;
    }
}

int main() {
    int m,n;
    cin>>m>>n;
    vector<vector<char>> tu(m,vector<char>(n));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>tu[i][j];
        }
    }
    
    vector<vector<int>> hang(m,vector<int> (3));
    vector<vector<int>> lie(n,vector<int> (3));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            char t=tu[i][j];
            if(t=='y'){
                hang[i][0]++;
                lie[j][0]++;
            }
            if(t=='o'){
                hang[i][1]++;
                lie[j][1]++;
            }
            if(t=='u'){
                hang[i][2]++;
                lie[j][2]++;
            }
        }
    }
    // print(hang);
    // cout<<endl;
    // print(lie);
    // cout<<endl;
    int64 res=0;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            
            char t=tu[i][j];
            if(t=='y'){
                int hango=hang[i][1];
                int hangu=hang[i][2];
                int lieo=lie[j][1];
                int lieu=lie[j][2];
                res+=hango*lieu;
                res+=hangu*lieo;
            }
            if(t=='o'){
                int hangy=hang[i][0];
                int hangu=hang[i][2];
                int liey=lie[j][0];
                int lieu=lie[j][2];
                res+=hangy*lieu+hangu*liey;
            }
            if(t=='u'){
                int hangy=hang[i][0];
                int hango=hang[i][1];
                int liey=lie[j][0];
                int lieo=lie[j][1];
                res+=hangy*lieo+hango*liey;
            }
            // cout<<i<<' '<<j<<' '<<res<<endl;
        }
    }
    cout<< res;


}



















// 64 位输出请用 printf("%lld")
发表于 2024-06-25 11:25:43 回复(0)
来_offer来头像 来_offer来
#include <iostream>
#include<vector>
#include<unordered_map>
using namespace std;

int main() {
    int n, m;
    cin>>n>>m;
    vector<vector<char>> damn(n,vector<char>(m));
    vector<unordered_map<char,int>> offer(m);
    vector<unordered_map<char,int>> row(n);
    for(int i=0;i<n;i++)
    {
        string a;
        cin>>a;
        for(int j=0;j<m;j++)
        {
            damn[i][j]=a[j];
            if(damn[i][j]=='y')
            {
                offer[j]['y']++;
                row[i]['y']++;
            }
            else
            {
                if(damn[i][j]=='o')
                {
                    offer[j]['o']++;
                    row[i]['o']++;
                }
                else
                {
                    if(damn[i][j]=='u')
                    {
                        offer[j]['u']++;
                        row[i]['u']++;
                    }
                }
            }
        }
    }
    long long int cnt=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(damn[i][j]=='y')
            {
                cnt+=row[i]['o']*offer[j]['u']+row[i]['u']*offer[j]['o'];
            }
            else {
                if(damn[i][j]=='o')
            {
                cnt+=row[i]['y']*offer[j]['u']+row[i]['u']*offer[j]['y'];           
            }
            else {
            if(damn[i][j]=='u')
            {
                cnt+=row[i]['o']*offer[j]['y']+row[i]['y']*offer[j]['o'];
            }
            }
            }
        }
    }
    cout<<cnt<<endl;
}
// 64 位输出请用 printf("%lld")
发表于 2025-03-24 20:20:10 回复(0)
MoonHoplite头像 MoonHoplite
记录每一行每一列有多少个 'y', 'o', 'u'。
暴力枚举直角顶点的位置，计算所在行列有多少个其余两个字母。例如直角顶点为 'y'，在第 r 行第c 列，第 r 行有 x1 个 'o', y1 个 'u'，第 c 列有 x2 个 'o', y2 个 'u'，则以这个点为直角顶点的满足条件的三角形有 x1 * y2 + x2 * y1 个。 
# Pypy3
m, n = list(map(int, input().split()))
 
row = [[0] * 3 for _ in range(m)]
col = [[0] * 3 for _ in range(n)]
valid_start = []
 
for r in range(m):
    s = input()
    for c, x in enumerate(s):
        if x in 'you':
            valid_start.append((r, c, x))
            if x == 'y':
                row[r][0] += 1
                col[c][0] += 1
            elif x == 'o':
                row[r][1] += 1
                col[c][1] += 1
            else:
                row[r][2] += 1
                col[c][2] += 1
 
ans = 0
for r, c, x in valid_start:
    if x == 'y':
        ans += row[r][1] * col[c][2] + row[r][2] * col[c][1]
    elif x == 'o':
        ans += row[r][0] * col[c][2] + row[r][2] * col[c][0]
    else:
        ans += row[r][0] * col[c][1] + row[r][1] * col[c][0]
         
print(ans)


发表于 2025-02-07 16:42:38 回复(1)
银色子弹1412头像 银色子弹1412 
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    long long int sum = 0;
    vector<vector<int>> isy(n, vector<int>(m));
    vector<vector<int>> iso(n, vector<int>(m));
    vector<vector<int>> isu(n, vector<int>(m));
    vector<int> cntRowY(n), cntRowO(n), cntRowU(n), cntLieY(m), cntLieO(m), cntLieU(m);
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++)
        {
            if (str[j] == 'y')
            {
                isy[i][j] = 1;
                cntRowY[i] ++;
                cntLieY[j] ++;
            }
            if (str[j] == 'o')
            {
                iso[i][j] = 1;
                cntRowO[i] ++;
                cntLieO[j] ++;
            }
            if (str[j] == 'u')
            {
                isu[i][j] = 1;
                cntRowU[i] ++;
                cntLieU[j] ++;
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (isy[i][j])
                sum += cntRowO[i] * cntLieU[j] + cntRowU[i] * cntLieO[j];
            else if (iso[i][j])
                sum += cntRowY[i] * cntLieU[j] + cntRowU[i] * cntLieY[j];
            else if (isu[i][j])
                sum += cntRowO[i] * cntLieY[j] + cntRowY[i] * cntLieO[j];
        }
    }

    cout << sum;


}
发表于 2024-10-09 19:57:21 回复(0)
哇哈哈asd头像 哇哈哈asd
记录每行每列y o u三个字符出现的次数，然后遍历直角顶点所在的位置（遍历二维数组），根据组合数学知识求解答案。 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt(), m = in.nextInt();
            char[][]grid = new char[n][m];
            int[] yRow = new int[n], yCol = new int[m], oRow = new int[n],
            oCol = new int[m], uRow = new int[n], uCol = new int[m];
            long ans = 0;
            for (int i = 0; i < n; i++) {
                String s = in.next();
                for (int j = 0; j < s.length(); j++) {
                    grid[i][j] = s.charAt(j);
                    if (grid[i][j] == 'y') {
                        yRow[i]++;
                        yCol[j]++;
                    }
                    if (grid[i][j] == 'o') {
                        oRow[i]++;
                        oCol[j]++;
                    }
                    if (grid[i][j] == 'u') {
                        uRow[i]++;
                        uCol[j]++;
                    }
                }
            }

            // 遍历直角顶点
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 'y') {
                        ans += oRow[i] * uCol[j] + uRow[i] * oCol[j];
                    }
                    if (grid[i][j] == 'o') {
                        ans += yRow[i] * uCol[j] + uRow[i] * yCol[j];
                    }
                    if (grid[i][j] == 'u') {
                        ans += yRow[i] * oCol[j] + oRow[i] * yCol[j];
                    }
                }
            }

            System.out.println(ans);
        }
    }
}
发表于 2025-04-14 18:48:22 回复(0)
提交观点

问题信息

难度：
6条回答 464浏览

热门推荐

相关试题

游游的you矩阵

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号