2021年寒假每日一題，2017~2019年的省賽真題，
本文內容由倪文迪（華東理pei工大學計算機系軟體192班）和羅勇軍老師提供，
后面的每日一題，每題發一個新博文，請大家看博客目錄：https://blog.csdn.net/weixin_43914593
文章目錄
- 1、題目大意
- 2、題解
- 3、C++代碼
- 4、Java代碼
- 5、Python代碼
題目：方格分割 http://oj.ecustacm.cn/problem.php?id=1320
??2017年藍橋杯軟體類省賽C++語言大學A組第4題，一道填空題，
1、題目大意
??6x6的方格，沿著格子的邊線剪開成兩部分，要求這兩部分的形狀完全相同，
??試計算：一共有多少種不同的分割方法，注意：旋轉對稱的屬于同一種分割法，
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/246067.html
標籤：java