迷你滨

用户名：uq_20629230267

访问量：9282

签　名：

等　　级
排　　名	2135
经　　验	2437
参赛次数	0
文章发表	13
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2023年第十四届省赛真题-网络稳定性(最大生成树+LCA)
浏览：1425

你可能喜欢

正解（暴力bfs）

　　作者: 迷你滨　　　　发表时间：2023-04-28 10:23:47 浏览：868　|　评论：2　

原题链接：蓝桥杯2023年第十四届省赛真题-合并区域

### 蓝桥杯2023年第十四届省赛真题-合并区域（暴力bfs）
已更新std。
原先错误std以为只能合并两块，殊不知可以有不止两块合并。

考虑暴力$$bfs$$。围绕一块地建图，另一块地在其周围旋转并移动，遍历bfs。遍历至多$$4\*4\*100=1600$$次，每次bfs复杂度$$O(100\*100)$$，总复杂度$$O(1600\*10000)=O(16e6)$$.

$$2s$$内足够了。
```java
import java.io.*;
import java.util.*;
  
public class Main {
    static int maxn = 200005,n,m;
    static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
    static Scanner sc = new Scanner (System.in);
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st  =new StreamTokenizer(bf);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[]args) throws IOException{
        int T = 1;
        while(T-->0) solve();
        pw.flush();
    }
    static final int I() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
      
    static int [][]g = new int [500][500];
    static int w[][] = new int [55][55];
    static boolean f[][] = new boolean [500][500];
    static int x1,x2,y1,y2;
      
    static void clear(int a,int b) {
        for(int i=a;i<a+n ; i++)
            for(int j=b;j<b+n;j++) g[i][j]=0;
    }
      
    static void add(int a,int b,int op) {
        if(op == 0) {
            for(int i=a;i<a+n ; i++)
                for(int j=b;j<b+n;j++) g[i][j]=w[i-a][j-b];
        }
        else if(op == 1) { //逆时针1次
            for(int j = b,u = 0 ; j <b+n ; j++,u++)
                for(int i = a+n-1,v=0 ; i>=a ; i--,v++) g[i][j] = w[u][v];
        }
        else if(op == 2) { //顺时针1次
            for(int j = b+n-1,u = 0 ; j>=b ; j--,u++)
                for(int i = a,v=0 ; i<a+n ; i++,v++) g[i][j] = w[u][v];
        }
        else { //倒置
            for(int i = a+n-1,u = 0 ; i >=a ; i--,u++)
                for(int j = b+n-1,v=0 ; j>=b ; j--,v++) g[i][j] = w[u][v];
        }
    }
      
    static void ppp() {
        System.out.println("graph:");
        for(int i=x1;i<=x2 ; i++) {
            for(int j=y1;j<=y2 ; j++) {
                System.out.print(g[i][j]+" ");
            }
            System.out.println();
        }
    }
      
    static int x[] = {1,-1,0,0};
    static int y[] = {0,0,1,-1};
      
    static int bfs(int aa,int bb) {
        Queue<Integer> q = new LinkedList<>();
        q.add(aa*1000+bb);
        int res=0;
        while(!q.isEmpty()) {
            int k = q.poll();
            int a = k/1000,b=k%1000;
            if(f[a][b]) continue;
            res++;
            f[a][b]=true;
            for(int i=0;i<4;i++) {
                int xx = a+x[i],yy = y[i]+b;
                if(xx>=x1 && xx<=x2 && yy>=y1 && yy <=y2 && !f[xx][yy] && g[xx][yy] == 1)
                    q.add(xx*1000+yy);
            }
        }
        return res;
    }
      
    static void work() {
        int res = 0;
        for(int u = x1 ; u <= x2 ; u++)
            for(int v=y1;v<=y2 ; v++) f[u][v]=false;
        for(int u = x1 ; u <= x2 ; u++)
            for(int v=y1;v<=y2 ; v++)
                if(g[u][v] == 1 && !f[u][v]) {
                    res = Math.max(res, bfs(u,v));
                }
        m=res;
        ans = Math.max(ans, res);
    }
      
    static void solve() throws IOException{
        n = I();
        for(int i = 60 ; i<60+n ; i++) //第一块区域固定，左上角为 (60,60)
            for(int j = 60 ; j<60+n ; j++)
                g[i][j] = I();
        for(int i = 0;i<n ; i++)
            for(int j = 0 ; j <n ; j++)
                w[i][j] = I();
          
          
        for(int i = 60-n+1 ; i <= 60+n-1 ; i++) { //上
            for(int j=0;j<4;j++) {
                add(60-n,i,j);
                x1 =60-n;y1 = Math.min(60, i); x2 = 60+n-1; y2 = Math.max(60+n-1, i+n-1);
                //ppp();
                work();
                //System.out.println(m);
                clear(60-n,i);
            }
        }
        for(int i = 60-n+1 ; i <= 60+n-1 ; i++) { //下
            for(int j=0;j<4;j++) {
                add(60+n,i,j);
                x1 =60;y1 = Math.min(60, i); x2 = 60+2*n-1; y2 = Math.max(60+n-1, i+n-1);
                //ppp();
                work();
                //System.out.println(m);
                clear(60+n,i);
            }
        }
        for(int i = 60-n+1 ; i <= 60+n-1 ; i++) { //左
            for(int j=0;j<4;j++) {
                add(i,60-n,j);
                  
                x1 =Math.min(i, 60);y1 = 60-n; x2 = Math.max(i+n-1, 60+n-1); y2 = 60+n-1;
                //ppp();
                work();
                //System.out.println(m);
                clear(i,60-n);
            }
        }
        for(int i = 60-n+1 ; i <= 60+n-1 ; i++) { //右
            for(int j=0;j<4;j++) {
                add(i,60+n,j);
                x1 =Math.min(i, 60);y1 = 60; x2 = Math.max(i+n-1, 60+n-1); y2 = 60+2*n-1;
                //ppp();
                work();
                //System.out.println(m);
                clear(i,60+n);
            }
        }
        pw.println(ans);
    }
}

```
恶心人的题。

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

徂川

我懂是啥了，丢脸了

2023-05-02 22:39:46

徂川

12行的T-->0是什么意思？

2023-05-02 22:09:54

迷你滨

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

整除问题（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

正解（暴力bfs）

评论区

精彩推荐

简单编码（C++代码）

C语言训练-数字母（C语言代码）

C语言训练-求素数问题（C语言代码）

买不到的数目（C++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

哥德巴赫曾猜测（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

迷你滨

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

整除问题 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

正解（暴力bfs）

评论区

精彩推荐

简单编码 （C++代码）

C语言训练-数字母 （C语言代码）

C语言训练-求素数问题 （C语言代码）

买不到的数目 （C++代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

整除问题（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

简单编码（C++代码）

C语言训练-数字母（C语言代码）

C语言训练-求素数问题（C语言代码）

买不到的数目（C++代码）

哥德巴赫曾猜测（C语言代码）