import java.util.Scanner;
//切割
public class Main{private static int max;
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
if (n == m){System.out.print("1");
return;
}
//创建矩形地图
int[][] rectangle = new int[n][m];
//按照1*1的正方形切割的到大值
max = n*m;
//记录切割的正方形数量 初始值为0
int count = 0;
backTrack(rectangle,0,0,0,n,m);
System.out.println(max);
}
public static void backTrack(int[][] rectangle,int count,int row,int col,int n,int m){//终止条件
if (count >max) return;
//寻找下一个像素的开始位置 找到就退出
Find:
for (row =0; row< n ; row++) {for (col =0; col< m ; col++) {//更新row和col
if (rectangle[row][col] == 0){break Find;
}
}
}
//判断当前是否切割完成
if (row == n && col == m){max=max >count? count:max;
return;
}
//进行切割操作 先定义边长
int edge = Math.min(n-row,m-col);
int flag=0;
for (int i = edge; i >0; i--) {for (int j = row; jfor (int k = col; k< col +i ; k++) {if (rectangle[j][k] == 1)flag =1;
}
}
//如果无法填充 则退出循环 否则填充且深入
if (flag == 1){continue ;
}
for (int j = row; jfor (int k = col; k< col +i ; k++) {rectangle[j][k] = 1;
}
}
backTrack(rectangle,count+1,row,col,n,m);
//撤回状态
for (int j = row; jfor (int k = col; k rectangle[j][k] =0;
}
}
}
}
}
C++#includeusing namespace std;
int map[20][20];
int ans=15*15;
int dfs(int n,int m,int num){
if(num>=ans) return 0;
if(n==m){
ans=1;
return 0;
}
int x,y,empty=0;
for(int i=0;i=1;add--){
bool unlable=true;
for(int i=x;i>n>>m;
for(int i=0;i
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
新闻标题:【06切割钢板】-创新互联
分享地址:http://www.cdkjz.cn/article/dcgesd.html