倪文迪陪你学藍橋杯2021冬休み毎日一題:1.20日(2018省試合A組第8題)

2021年冬休み毎日1題、2017~2019年の省試合本題.本文の内容は倪文迪(華東理工大学コンピュータ学部ソフトウェア192班)と羅勇軍先生から提供された.後の毎日1題、毎回新しい博文を出して、皆さんは毎日ブログのブルーブリッジカップコラムを見てください.https://blog.csdn.net/weixin_43914593/category_10721247.html
C++、Java、Pythonの3言語のコードを提供します.
文書ディレクトリ

1、題名説明

2、題解

3、DFSのC++コード

4、BFSのPythonコード

5、Javaコード

2018省試合A組第8題「地球温暖化」、テーマリンク:http://oj.ecustacm.cn/problem.php?id=1365 https://www.dotcpp.com/oj/problem2276.html
1、テーマの説明
ある海域のNxN画素の写真を持っています.「.」は陸地を表しています.以下に示します.

.......
.##....
.##....
....##.
..####.
...###.
.......

このうち「上下左右」の4つの方向につながっている陸地が島を構成している.例えば上図には2つの島があります.地球温暖化で海面が上昇したため、科学者は今後数十年間、島の縁の1画素の範囲が海水に水没すると予測している.具体的には、陸地画素が海洋に隣接している(上下左右4つの隣接画素のうち海洋がある)と、水没する.例えば、上図の海域は将来次のようになります.

.......
.......
.......
.......
....#..
.......
.......

科学者の予測によると、写真の中にどれだけの島が完全に水没するか計算してください.入力:最初の行には整数Nが含まれます.(1 <= N <= 1000) .以下のN行N列は海域写真を表す.写真は1行目、1列目、N行目、N列目の画素が海洋であることを保証します.出力:整数で答えを表します.
2、問題解
タイトルを見ると「連通ブロック問題」であり,基礎検索である.DFSまたはBFSを使用してもよい:1つの連通ブロックを巡回する(この連通ブロックのすべての'#'、検索済みとマークし、検索しなくてもよい);次の連通ブロックを巡回する...;すべての連通ブロックを巡回し、何個の連通ブロックがあるかを統計する.
テーマに戻ると、どんな島が完全に水没しないのですか?島の中に陸地(高地と称する)があり、その周囲が陸地であれば、この島は完全に水没しない.(N^2)O(N 2)の、もっと良くなるはずがない.  次はC++コードでDFSを実現し、PythonでBFSを実現し、Javaコードを添付します.
3、DFSのC++コード
  DFSのすべての点は、'#'に出会ったら、DFSという'#'周囲の'#'を続けます.検索した'#'を検索したとマークし、検索する必要はありません.高地のない島の数をマークするのが答えです.

#include
using namespace std;

int n;
char a[1010][1010]; //  
int vis[1010][1010]={
     0};  //      
int d[4][2] = {
     {
     0,1}, {
     0,-1}, {
     1,0}, {
     -1,0}}; //    
int flag;  //               
void dfs(int x, int y){
     
    vis[x][y] = 1;      //    '#'   。           
    if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')
        flag = 1;       //        ，    
    for(int i = 0; i < 4; i++){
      //  DFS     
        int nx = x + d[i][0], ny = y + d[i][1];
      //if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==0 && a[nx][ny]=='#') //        ，        
        if(vis[nx][ny]==0 && a[nx][ny]=='#') //  DFS      ，       
            dfs(nx,ny);
    }
}

int main(){
     
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
    int ans = 0 ;
    for(int i = 1; i <= n; i++)  //DFS     
        for(int j = 1; j <= n; j++)
            if(a[i][j]=='#' && vis[i][j]==0){
     
                flag = 0;
                dfs(i,j);
                if(flag == 0)  //       
                    ans++;     //      
            }
    cout<<ans<<endl;
    return 0;
}

4、BFSのPythonコード
  の下のコードはBFSを実現した.注意Pythonには2つのキュー実装方式があります.  (1)queueでキュー操作を実装します.次のコードを参照してください.  (2)Pythonのlistは普通のキューで、コードの注釈はlistで実装されたキューです.

from queue import *

def bfs(x,y):
    dirt=[(0,1),(0,-1),(1,0),(-1,0)]    
    q = Queue()               #q = [(x,y)]   #    list     
    q.put((x,y))
    vis[x][y]=1
    flag = 0    
    
    while not q.empty():      #while len(q)!=0:        
        current=q.get()       #current=q.pop(0)
        x,y=current[0],current[1]
        if flag == 0:
          if a[x][y+1]=='#' and a[x][y-1]=='#' and a[x+1][y]=='#' and a[x-1][y]=='#':
             flag = 1                             #       
        
        for i in range(4):
            newx=x+dirt[i][0]
            newy=y+dirt[i][1]
            if vis[newx][newy]==0 and a[newx][newy]=="#":                              
               q.put((newx,newy))   #q.append((newx,newy))
               vis[newx][newy]=1                  #         
    if flag == 0:                                 #     
        return True
    return False                                  #      
n=int(input())
a=[]
for i in range(n):
    a.append(list(input()))
vis=[]
for i in range(n):
    vis.append([0]*n) 
ans=0
for i in range(n):
    for j in range(n):
        if vis[i][j]==0 and a[i][j]=="#":  
            if bfs(i,j):   #     
                ans+=1
print(ans)

5、Javaコード
  の下のJavaコードはBFSを実現した.

//http://oj.ecustacm.cn/ User: 1840131230
import java.math.BigInteger;
import java.util.*;
public class Main 
{
     
    static class node{
     
        int x,y;
        node(int x,int y){
     
            this.x=x;
            this.y=y;
        }
    }
    static int n,sums=0;
    static char map[][];
    static int vist[][];
    static int dx[]= {
     0,0,-1,1};
    static int dy[]= {
     -1,1,0,0};
    static void bfs(int x,int y) {
     
        Queue<node> que=new LinkedList<node>();
        que.add(new node(x,y));
        vist[x][y]=1;
        boolean flag=true;
        while(!que.isEmpty()) {
     
            node p=que.remove();
            int xx=p.x;
            int yy=p.y;
            int sum=0;
            for(int i=0;i<4;i++) {
     
                int xxx=xx+dx[i];
                int yyy=yy+dy[i];
                if(xxx>=0&&xxx<n&&yyy>=0&&yyy<n&&map[xxx][yyy]=='#') {
     
                    sum++;
                }
            }
            if(sum==4)flag=false;
            for(int i=0;i<4;i++) {
     
                int xxx=xx+dx[i];
                int yyy=yy+dy[i];
                if(xxx>=0&&xxx<n&&yyy>=0&&yyy<n&&vist[xxx][yyy]==0&&map[xxx][yyy]=='#') {
     
                    vist[xxx][yyy]=1;
                    que.add(new node(xxx,yyy));
                    sum++;
                }
            }
             
        }
        if(flag)sums++;
    }
    public static void main(String[] args) 
    {
     
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        map=new char[n][n];
        vist=new int[n][n];
        for(int i=0;i<n;i++) {
     
            map[i]=sc.next().toCharArray();
        }
        for(int i=0;i<n;i++) {
     
            for(int j=0;j<n;j++) {
     
                if(map[i][j]=='#'&&vist[i][j]==0) {
     
                    bfs(i,j);
                }
            }
        }
        System.out.println(sums);
    }
}