本文共 2755 字，大约阅读时间需要 9 分钟。

剪邮票问题可视化为图形中寻找五个互相连接的点的问题。该图形由12张邮票组成，呈现3行4列的结构。用户的目标是从中剪取五张连续连接的邮票，仅仅连接一个边不算连续。

问题分析

将邮票排列的二维坐标视为一个3行4列的网格点。每个点的坐标为(i, j)，其中i范围[1,3]，j范围[1,4]。需要从中选择五个点，使得这五个点彼此连贯（上下左右相邻），无孤立点。

方法思路

针对该问题，可以采用广度优先搜索（BFS）遍历图形。首先，确定起点和终点，然后使用BFS检查是否所有点都被访问到。

解决代码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class L2016剪邮票 {
    static boolean vis[][] = new boolean[3][4];
    static int mp[][] = new int[3][4];
    static int dx[] = { -1, 0, 1, 0 };
    static int dy[] = { 0, -1, 0, 1 };
    static class d {
        int x;
        int y;
        public d(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static Queue
   
     q = new LinkedList<>();
    static d end;
    static void init() {
        for (int i = 0; i < 3; i++) {
            Arrays.fill(vis[i], false);
            Arrays.fill(mp[i], -1); // 障碍
        }
    }
    static boolean Check(int x, int y) {
        if (x >= 0 && y >= 0 && x < 3 && y < 4 && mp[x][y] != -1)
        return true;
        return false;
    }
    static void bfs(int x, int y) {
        end = new d(x, y);
        q.add(end);
        while (!q.isEmpty()) {
            d now = q.poll();
            for (int i = 0; i < 4; i++) {
                int xx = now.x + dx[i];
                int yy = now.y + dy[i];
                if (Check(xx, yy) && !vis[xx][yy]) {
                    vis[xx][yy] = true;
                    d next = new d(xx, yy);
                    q.add(next);
                }
            }
        }
    }
    public static void main(String[] args) {
        int ans = 0;
        for (int i = 0; i < 12; i++) {
            for (int j = i + 1; j < 12; j++) {
                for (int k = j + 1; k < 12; k++) {
                    for (int l = k + 1; l < 12; l++) {
                        for (int m = l + 1; m < 12; m++) {
                            init();
                            mp[i/4][i%4] = 1;
                            mp[j/4][j%4] = 1;
                            mp[k/4][k%4] = 1;
                            mp[l/4][l%4] = 1;
                            mp[m/4][m%4] = 1;
                            vis[i/4][i%4] = true;
                            bfs(i/4, i%4);
                            if (vis[i/4][i%4] && vis[j/4][j%4] 
                                    && vis[k/4][k%4] && vis[l/4][l%4] 
                                    && vis[m/4][m%4]) {
                                ans++;
                            }
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}
   

答案

经过计算，共有116种不同的剪取方法。

感受

这道题在于将实际问题转化为图的遍历问题，通过BFS验证连通性。暴力枚举虽然不够优化，但在小规模数据下仍然有效。

转载地址：http://mjiuk.baihongyu.com/