【蓝桥真题5】带三百人训练了十天精选蓝桥真题，看看他们都练些什么（三门语言题解）（中）

2022-05-22 93

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【蓝桥真题5】带三百人训练了十天精选蓝桥真题，看看他们都练些什么（三门语言题解）

🍃5.回文日期

题目链接：回文日期 http://lx.lanqiao.cn/problem.page?gpid=T2856

一道代码量比较大的模拟题，考察的又是时间的处理，这里我同样套用之前蓝桥真题中讲过的日期模拟模板。模拟能力是一项考察算法能力很基础的一项，一旦代码量一大许多同学就会在各种地方出现问题，而且由于代码量大能以发现问题。如果能AC这题相信对你的模拟能力有很大的提升，我们直接来看代码转换：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
  static int[] M={0,31,28,31,30,31,30,31,31,30,31,30,31};
  static int a;
  static int b;
  public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  List<Integer> list=new ArrayList<>();
  while(n!=0) {
    list.add(0,n%10);
    n/=10;
  }
  int y=list.get(0)*1000+list.get(1)*100+list.get(2)*10+list.get(3);
  int m=list.get(4)*10+list.get(5);
  int d=list.get(6)*1+list.get(7);
  boolean flag1=true;
  boolean flag2=true;
  String anser1="";
  String anser2="";
  while(flag1||flag2) {
    if(y%400==0||(y%4==0&&y%100!=0)) {
    M[2]=29;
    }else {
    M[2]=28;
    }
    d++;
    if(d>M[m]) {
    d=1;
    m++;
    }
    if(m>12) {
    m=1;
    y++;
    }
    if(check1(y,m,d)&&flag1) {
    anser1=test(y,m,d);
    flag1=false;
    }
    if(check2(y,m,d)&&flag2) {
    anser2=test(y,m,d);
    flag2=false;
    }
  } 
  System.out.println(anser1);
  System.out.println(anser2);
}
   static boolean check1(int y,int m,int d) {
    String sb=test(y,m,d);
    int n=sb.length();
    int l=0;
    int r=n-1;
    while(l<r) {
     if(sb.charAt(l++)!=sb.charAt(r--)) return false;
    }
    return true;
   }
   static boolean check2(int y,int m,int d) {
    String sb=test(y,m,d);
    char a1=sb.charAt(0);
    char b1=sb.charAt(1);
    char c1=sb.charAt(2);
    char d1=sb.charAt(3);
    char e1=sb.charAt(4);
    char f1=sb.charAt(5);
    char g1=sb.charAt(6);
    char h1=sb.charAt(7);
    return a1!=b1&&a1==c1&&c1==f1&&f1==h1&&b1==d1&&d1==e1&&e1==g1;
   }
   static String test(int y,int m,int d) {
    StringBuilder sb=new StringBuilder();
    sb.append(y);
    if(m<10) {
     sb.append("0"+m);
    }else {
     sb.append(m);
    }
    if(d<10) {
     sb.append("0"+d);
    }else {
     sb.append(d);
    }
    return sb.toString();
   }
}

🍂6.全球变暖

你有一张某海域NxN像素的照片，"."表示海洋、"#"表示陆地，如下所示：

.......

.##....

....##.

..####.

...###.

.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......

....#..

.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

题目链接：全球变暖http://lx.lanqiao.cn/problem.page?gpid=T2746

题目可以用深搜和广搜来做，我们套模板即可。深搜和广搜的重要性不言而喻，这道题大家拿来练手是非常合适的。无论是深搜还是广搜，每次我们遍历一个岛屿时，都要判断这个岛屿是否存在上下左右都是陆地的的陆地。这里要注意的是由于深搜会进行栈递归，在最后一个大数据的情况下会爆栈，而广搜就没有这个问题。下面贴上两种代码

深度优先搜索：

import java.util.Scanner;
public class Main {
  static int[] dx= {1,-1,0,0};
  static int[] dy= {0,0,1,-1};
  static boolean[][] visit;
  static int ans=0;
  static boolean flag=false;
  public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  char[][] arr=new char[n][n];
  for(int i=0;i<n;++i) {
    arr[i]=sc.next().toCharArray();
  }
  visit=new boolean[n][n];
  for(int i=0;i<n;++i) {
    for(int j=0;j<n;++j) {
    if(arr[i][j]=='#'&&!visit[i][j]) {
      dfs(arr,i,j);
      if(!flag) ans++;
      flag=false;
    }
    }
  }
  System.out.println(ans);
  }
  static void dfs(char[][] arr,int a,int b) {
  if(check(arr,a+dx[0],b+dy[0])&&check(arr,a+dx[1],b+dy[1])&&check(arr,a+dx[2],b+dy[2])&&check(arr,a+dx[3],b+dy[3])) {
    flag=true;
  }
  visit[a][b]=true;
  for(int i=0;i<4;++i) {
    int newX=a+dx[i];
    int newY=b+dy[i];
    if(arr[newX][newY]=='#'&&!visit[newX][newY])  dfs(arr,newX,newY);
  }
  }
  static boolean check(char[][] arr,int i,int j) {
  return arr[i][j]=='#';
  }
}

宽度优先搜索：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
  static int[] dx= {1,-1,0,0};
  static int[] dy= {0,0,1,-1};
  static boolean[][] visit;
  static int ans=0;
  static boolean flag=false;
  public static void main(String[] args) {
  Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  char[][] arr=new char[n][n];
  for(int i=0;i<n;++i) {
    arr[i]=sc.next().toCharArray();
  }
  visit=new boolean[n][n];
  for(int i=0;i<n;++i) {
    for(int j=0;j<n;++j) {
    if(arr[i][j]=='#'&&!visit[i][j]) {
      Queue<int[]> queue=new LinkedList<>();
      queue.offer(new int[] {i,j});
      visit[i][j]=true;
      dfs(arr,queue);
      if(!flag) ans++;
      flag=false;
    }
    }
  }
  System.out.println(ans);
  }
  static void dfs(char[][] arr,Queue<int[]> queue) {
   while(!queue.isEmpty()) {
    int size=queue.size();
    while(size-->0) {
     int[] curr=queue.poll();
     int a=curr[0];
     int b=curr[1];
     if(check(arr,a+dx[0],b+dy[0])&&check(arr,a+dx[1],b+dy[1])&&check(arr,a+dx[2],b+dy[2])&&check(arr,a+dx[3],b+dy[3])) {
      flag=true;
      }
     for(int i=0;i<4;++i) {
      int newX=a+dx[i];
      int newY=b+dy[i];
      if(arr[newX][newY]=='#'&&!visit[newX][newY]){
       visit[newX][newY]=true;
       queue.offer(new int[] {newX,newY});
      }
     }
    }
   }
  }
  static boolean check(char[][] arr,int i,int j) {
  return arr[i][j]=='#';
  }
}