倪文迪陪你学蓝桥杯2021寒假每日一题:1.6日(2017省赛A第4题)

时间:2021-1-8 作者:admin

2021年寒假每日一题,2017~2019年的省赛真题。
本文内容由倪文迪(华东理pei工大学计算机系软件192班)和罗勇军老师提供。

后面的每日一题,每题发一个新博文,请大家看博客目录https://blog.csdn.net/weixin_43914593

文章目录

题目:方格分割 http://oj.ecustacm.cn/problem.php?id=1320
  2017年蓝桥杯软件类省赛C++语言大学A组第4题,一道填空题。

1、题目大意

  6×6的方格,沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。
  试计算:一共有多少种不同的分割方法。注意:旋转对称的属于同一种分割法。

2、题解

  又是暴搜。第1题DFS,第2题BFS,第3题BFS,这题又回到DFS。下一题估计是BFS?
  
  倪文迪的话:“这道题可能上来会想到搜格子,但搜格子意味着更高的复杂度以及判连通的需要,本题似乎搜索要切开的边更优。由题意,这一条切割线必定经过图的中心点,那么我们一旦确定了半条到达边界的分割线,就能根据这半条对称画出另外半条。而由于结果中心对称性,搜索出来的个数应该除以4得出最终结论。在搜索过程中需要注意的是,我们搜索出的半条分割线不能同时经过关于中心对称的两个点,所以在标记时,需要将对称的点也标上。”
  中心点是(3,3),从(3,3)出发,向右、向左、向上、向下,四个方向DFS即可。
  
  下面给出三种语言的代码。
  据说Python组参加人少,容易得奖。Python真是好,Python呱呱叫。

3、C++代码

倪文迪的代码:

#include<bits/stdc++.h>
using namespace std;

int X[] = {0, -1, 1, 0, 0};
int Y[] = {0, 0, 0, -1, 1};

bool vis[10][10];
int res = 0;

void dfs(int x, int y){
	if(x == 0 || y == 0 || x == 6 || y == 6){
		res++;
		return ;
	}
	for(int i = 1 ; i <= 4 ; i++){   //上下左右四个方向
		x += X[i]; y += Y[i];        //走一步
		if(!vis[x][y]){       // 若该点未访问则继续深搜
			vis[x][y] = true;  //  当前的点标注为已访问
			vis[6 - x][6 - y] = true;
			dfs(x, y);         // 继续深搜
			vis[6 - x][6 - y] = false;
			vis[x][y] = false;
		}
		x -= X[i]; y -= Y[i];
	}
}

int main(){
	vis[3][3] = true;
	dfs(3, 3);
	cout << res / 4 << endl;
	return 0;
}

4、Java代码

http://oj.ecustacm.cn/用户20185012的代码:

public class Main { 
    private static int ans = 0;
    private static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    private static boolean[][] visit = new boolean[7][7];
 
    public static void main(String[] args) {
        visit[3][3] = true;
        dfs(3,3);
        System.out.println(ans / 4);
    }
 
    private static void dfs(int x,int y){
        if (x == 0 || y == 0 || x == 6 || y == 6){
            ans ++;
            return;
        }
        visit[x][y] = true;
        visit[6 - x][6 - y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if (nx < 0 || nx > 6 || ny < 0 || ny > 6)
                continue;
            if (!visit[nx][ny])
                dfs(nx,ny);
        }
 
        visit[x][y] = false;
        visit[6 - x][6 - y] = false;
    }
}

5、Python代码

http://oj.ecustacm.cn/用户20192031003的代码:

count = 0
vis = [[1] * 7 for i in range(7)]
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)] 
 
def dfs(x, y):
    global count
    if x == 0 or y == 0 or x == 6 or y == 6:
        count += 1
        return
    # 当前点和对称点都标注访问
    vis[x][y], vis[6 - x][6 - y] = 0, 0
    for i in range(0, 4):
        # 新坐标
        newx = x + dir[i][0]
        newy = y + dir[i][1]
        if newx < 0 or newx > 6 or newy < 0 or newy > 6:
            continue
        if vis[newx][newy]:
            dfs(newx, newy)
    vis[x][y], vis[6 - x][6 - y] = 1, 1 
 
dfs(3, 3)
print(count//4)
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。