首页 > 试题广场 >

照镜子

[编程题]照镜子
  • 热度指数：1332 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

小团有一个的矩阵A， 他知道这是小美用一种特殊的方法生成的，具体规则如下:

小美首先写下一个的矩阵，然后小美每一次将这个矩阵上下翻转后接到原矩阵的下方。小美重复这个过程若干次（甚至可能是0次，也就是没有进行过这一操作），然后将操作后的矩阵交给小团。

小团想知道，小美一开始写下的矩阵是什么。因为小美可能有多种一开始的矩阵，小团想得到最小的矩阵（这里的最小指矩阵即的面积最小）。


输入描述:
输入包含两个整数n,m，表示小团矩阵的大小。
接下来n行，每行m个正整数，第i行第j列表示矩阵第i行第j列的数。


输出描述:
输出包含一个矩阵，一共n'行m列，表示小美一开始最小的矩阵。
示例1

输入

8 3
1 0 1
0 1 0
0 1 0
1 0 1
1 0 1
0 1 0
0 1 0
1 0 1

输出

1 0 1
0 1 0

说明

小美一开始的矩阵可能有以下3种：
1.
1 0 1
0 1 0
2.
1 0 1
0 1 0
0 1 0
1 0 1
3.
1 0 1
0 1 0
0 1 0
1 0 1
1 0 1
0 1 0
0 1 0
1 0 1
其中最小的矩阵为第一种。

备注:
对于40%的数据，
对于100%的数据，,矩阵内的数小于等于10
算法知识视频讲解
添加回答
pein531头像 pein531
(1) 原始矩阵是奇数行：那小美肯定就没有进行过操作，输出现在的矩阵就好。
(2) 原始矩阵是偶数行：先检查原始矩阵上半部分和下半部分是不是镜像对称的。如果是，矩阵规模就折半再检查（因为下半部分是翻转得到的，所以再检查上半部分），否则输出当前的矩阵。 
def solve(h):
    if h % 2 == 0:
        # h是偶数，就检查一下上下两半是不是镜像的
        for i in range(h // 2):
            if matrix[i] != matrix[h - i - 1]:
                # 对称性已经不满足，现在的矩阵就是最小的
                return h
        # 如果这个h符合要求，就折半再检查找更小的
        return solve(h // 2)
    else:
        # 如果n是奇数，那小美肯定没有操作过，现在的矩阵就是原矩阵
        return h

if __name__ == "__main__":
    n, m = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(n)]
    h = solve(n)
    for i in range(h):
        for j in range(m):
            print(matrix[i][j], end=" ")
        print()


发表于 2021-03-03 23:47:17 回复(3)
云云云一飞冲天头像 云云云一飞冲天
这个不是无脑贪心嘛？
用字符串数组，然后遍历找，找到相同点就记录位置然后跳出，这个位置就是一个最小对称，除以二就是最小矩阵，输出即可；
反正是都通过了，姑且认为是对的吧
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] int1 = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = int1[0];
        int m = int1[1];
        String[] map = new String[n];
        for (int i = 0; i < n; i++) {
            map[i] = br.readLine();
        }
        int flag = 0;
        for (int i = 1; i < n; i++) {
            if (map[i].equals(map[0])) {
                flag = i;
                break;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= flag / 2; i++) {
            sb.append(map[i]);
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

发表于 2022-09-04 18:48:02 回复(0)
牛客614649312号头像 牛客614649312号 
var data = readline().split(" ").map(item=>parseInt(item));
var n = data[0];
var m = data[1];
var res = [];
var flag = [];
 
for(var i=0;i<n;i++){
    data = readline();
    if(res.includes(data)){
        flag.push(data);
    }else{
        res.concat(flag);
        res.push(data);
        flag = [];
    }
}
res.forEach(item=>{
    console.log(item);
})


发表于 2022-08-26 21:12:33 回复(0)
牛客631740696头像 牛客631740696
这题能用HashSet吗
发表于 2022-07-08 09:35:56 回复(0)
wonderson头像 wonderson 
import java.util.*;
public class Main {
         public static void main(String[] args) {
             Scanner sc = new Scanner(System.in);
             int m = sc.nextInt(), n = sc.nextInt();
             if (m == 0 || n == 0) {
                 return;
             }
             int[][] nums = new int[m][n];

             for (int i = 0; i < m; i++) {
                 for (int j = 0; j < n; j++) {
                     nums[i][j] = sc.nextInt();
                 }
             }
             sc.close();
             
             if (m % 2 != 0) {
                 for (int i = 0; i < m; i++) {
                     print(nums[i]);
                 }
                 return;
             }

             int cur = m / 2;
             loop: while (cur > 0) {
                 int other = cur * 2 - 1;
                for (int i = 0; i < cur; i++) {
                    if (!comp(nums, i, other - i)) {
                        break loop;
                    }
                }
                 if (cur % 2 == 1) {
                     for (int i = 0; i < cur; i++) {
                         print(nums[i]);
                     }
                     return;
                 }
                cur /= 2;
             }
             int rows = cur > 0 ? cur * 2 : 1;  
             for (int i = 0; i < rows; i++) {
                 print(nums[i]);
             }
         }

         private static void print(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                System.out.print(nums[i] + " ");
            }
             System.out.println();
        }
         private static boolean comp(int[][] nums, int i, int j) {
             for (int k = 0; k < nums[i].length; k++) {
                 if (nums[i][k] != nums[j][k]) {
                     return false;
                 }
             }
             return true;
         }
     }

发表于 2022-04-12 18:32:40 回复(0)
LemonHuang头像 LemonHuang
卡时间的题，真恶心啊。
贴个JAVA版本。 
import java.io.*;

/**
 * @Author: LemonHuang
 */
public class Test03 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs1 = br.readLine().trim().split(" ");
        int n = Integer.parseInt(strs1[0]);
        int m = Integer.parseInt(strs1[1]);
        String[] strs = new String[n];
        for(int i = 0; i < n; i++){
            strs[i] = br.readLine().trim();
        }
        int len = helper(strs, n);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < len; i++){
            bw.write(strs[i]);
            bw.newLine();
        }
        bw.flush();
    }
    //递归寻找最小的长度
    private static int helper(String[] strs, int len){
        if(len % 2 == 1) return len; // 奇数
        //偶数
        for(int i = 0; i < len >> 1; i++){
            if(!strs[i].equals(strs[len - 1 - i])) return len;
        }
        //递归搜索更小的长度
        return helper(strs, len >> 1);
    }
}

发表于 2022-03-31 21:40:51 回复(0)
榔头在手头像 榔头在手
let [n,m] = readline().split(' ').map(Number)
 
let arr = new Array(n)
for(let i =0;i<n;i++){
    arr[i] = readline().split(' ').map(Number)
}
 
let n1 = n
let isBreak = false
while(n1%2 === 0 ){
    if(isBreak) break
    let top = 0, bottom = n1 -1
    while(top<bottom)   {
        for(let i =0; i< m;i++){
            if(arr[top][i] !== arr[bottom][i]){
                isBreak = true
                break
            }
        }
        top ++
        bottom --
    }
    if(isBreak) break
    n1 = n1/2
}
for(let i = 0;i< n1;i++){
    print(...arr[i])
}
发表于 2022-03-24 12:18:03 回复(0)
Hello_WordN头像 Hello_WordN 
#include<bits/stdc++.h>
using namespace std;
int osx=0,osy=0;
pair<int ,int> zheban(int n,int m,vector<vector<int>>arr)
{
 for(int i=0;i<n;i++)
   for(int j=0;j<m;j++)
   { 
     if(arr[i][j]!=arr[n-i-1][j])
     {  
       return {n,m};
     }
   }
  return zheban(n/2,  m,arr);//折半检测
  
}
int main()
{  int n,m;
 cin>>n>>m;
 vector<vector<int>>arr(n+1,vector<int>(m+1));
 for(int i=0;i<n;i++)
   for(int j=0;j<m;j++)
     cin>>arr[i][j];
 //以上是输入
 if(n&1==1)//判断是不是奇数
 {
   for(int i=0;i<n;i++)
   for(int j=0;j<m;j++)
     cout<<arr[i][j];
  }
 else
 {  pair<int, int>ast;
   ast=zheban(n,m,(arr));
   for(int i=0;i<ast.first;i++)
   {
     for(int j=0;j<ast.second;j++)
     {
       
     
       cout<<arr[i][j]<<' ';
   }
  cout<<endl;
 }
 }
return 0;   
  }
 
   

确实麻烦。。

编辑于 2022-03-04 16:40:23 回复(0)
王小新xin头像 王小新xin 
import java.util.*;
public class Main{
    static int count=0;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        sc.nextLine();
        String[] s=new String[n];
        for(int i=0;i<n;i++){
            s[i]=sc.nextLine();
        }
        for(int i=1;i<=n;i++){
            if(n%i==0){
                List<String> temp1=new ArrayList<>();
                for(int k=0;k<i;k++){
                    temp1.add(s[k]);
                 }
                int j=1;
                for(;j<n/i;j++){
                    List<String> temp2=new ArrayList<>();
                    for(int k=j*i;k<(j+1)*i;k++){
                        temp2.add(s[k]);
                    }
                    if(j%2!=0){
                        Collections.reverse(temp2);
                    }
                    if(!temp1.equals(temp2)){
                        break;
                    }
                }
                if(j==n/i){
                    for(String val:temp1){
                        System.out.println(val);
                    }
                    break;
                }
            }
        }
    }
}

发表于 2022-03-02 15:52:39 回复(0)
看星星呐头像 看星星呐 
n,m = map(int, input().split())
aim = [list(map(int, input().split())) for _ in range(n)]
flag = 1
while len(aim) % 2 == 0 and flag==1:
    for i in range(len(aim)//2):
        if aim[i] != aim[len(aim)-1-i]:
            flag = 0
            break
    else:aim = aim[:len(aim)//2]
for each in aim:
    for k in range(m):
        if k!=m-1:print(each[k],end=' ')
        else:print(each[k])
    print('',end='')

发表于 2021-09-01 09:44:02 回复(0)
JCoder头像 JCoder 
#include <bits/stdc++.h>
using namespace std;

int n, m, a[100005][5];

bool check(int n) {
    for (int i = 0; i < n / 2; i++) {
        int k = n - i - 1;
        for (int j = 0; j < m; j++) {
            if (a[i][j] != a[k][j]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    while (n % 2 == 0 && check(n)) {
        n /= 2;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (j) {
                printf(" ");
            }
            printf("%d", a[i][j]);
        }
        printf("\n");
    }

    return 0;
}

发表于 2021-08-30 19:55:17 回复(0)
刷完这题我就去睡觉头像 刷完这题我就去睡觉 
/**
 *      author:刷完这题就去睡觉
 *      created:
**/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Printf(vector<vector<int>>&a){
    int row=a.size(),col=a[0].size();
    for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                cout<<a[i][j]<<" ";
            }
            cout<<endl;
        }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<vector<int>>grid;
    for(int i=0;i<n;i++){
        grid.push_back(vector<int>());
        for(int j=0;j<m;j++){
            int temp;
            cin>>temp;
            grid[i].push_back(temp);
        }
    }
    if(n%2==1){
        Printf(grid);
        return 0;
    }
    bool flag=true;
    while(flag){
        int l=0,r=n-1;
        while(l<r){
            if(grid[l]!=grid[r]){
                flag=false;
                Printf(grid);
                return 0;
            }
            l++;
            r--;
        }
        n/=2;
        for(int i=1;i<=n;i++){
            grid.pop_back();
        }
    }
    return 0;
}

发表于 2021-08-15 22:01:04 回复(0)
辣🐓头像 辣🐓
//迭代折半比较，每一行字符串为一个单位，利用循环比较相对于数组首部和尾部相同距离的字符串是否相同，如果不相同则证明到此不是镜像数组，直接输出，如果直到比较到相邻的字符串也相等时，表示该数组为镜像数组，记录下最小的字符串数组的长度，通过迭代来减半数组长度再次比较，直到两个字符串不相等或者字符串长度==1，输出最小长度的字符串数组则为所求 
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int row = Integer.parseInt(s[0]);
        int col = Integer.parseInt(s[1]);
        String[] mirr = new String[row];
        for (int i = 0; i < row; i++) {
            mirr[i] = reader.readLine();
        }
        int cycle = mirr.length;
        out:for (int i = mirr.length;i>0;i/=2){
            in:for (int j = 0; j < i/2; j++) {
                if (!mirr[j].equals(mirr[i-j-1])){
                    cycle = Math.min(cycle,i);
                    break out;
                }
            }

        }
        for (int i = 0; i < cycle; i++) {
            writer.write(mirr[i]);
            writer.newLine();
        }
        writer.flush();

    }
}

发表于 2021-04-24 20:03:47 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 美团 前端工程师 算法工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
13条回答 2341浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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