正解（暴力bfs）

911 阅读 4 评论 0 点赞

原题链接：蓝桥杯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分

2 人评分

本文分类：题解列表
浏览次数：911 次浏览
发布日期：2023-04-28 10:23:47
本文链接：https://blog.dotcpp.com/a/96192

上一篇 > [编程入门]完数的判断
下一篇 > 计算鞍点计算鞍点计算鞍点计算鞍点

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

正解（暴力bfs）

评论列表共有 4 条评论

发表评论取消回复

正解（暴力bfs）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

评论列表共有 4 条评论

发表评论取消回复