剪格子

逃离我推掉我的手 2022-07-12 12:12 199阅读 0赞

package 搜索;  
  
  
import java.util.Scanner;  
  
  
public class 剪格子 \{  
static int arr\[\]\[\];  
static int n;  
static int m;  
static int result;  
static int x\[\] = \{ 1, 0, -1, 0 \};  
static int y\[\] = \{ 0, 1, 0, -1 \};  
static int half;  
static boolean\[\]\[\] flag;  
  
  
public static void main(String\[\] args) \{  
Scanner sc = new Scanner(System.in);  
m = sc.nextInt();  
n = sc.nextInt();  
result = n \* m;  
arr = new int\[n\]\[m\];  
flag = new boolean\[n\]\[m\];  
int sum = 0;  
int max = 0;  
for (int i = 0; i < n; i++) \{  
for (int j = 0; j < m; j++) \{  
arr\[i\]\[j\] = sc.nextInt();  
sum += arr\[i\]\[j\];  
if (arr\[i\]\[j\] > max)  
max = arr\[i\]\[j\];  
\}  
\}  
  
  
half = sum / 2;  
if (half \* 2 != sum || max > half) \{  
System.out.println(0);  
return;  
\}  
f();  
\}  
  
  
private static void f() \{  
for (int i = 0; i < n; i++)  
for (int j = 0; j < m; j++) \{  
dfs(i, j, 1);  
\}  
System.out.println(result == n \* m ? 0 : result);  
\}  
  
  
private static void dfs(int row, int col, int count) \{  
flag\[row\]\[col\] = true;  
half -= arr\[row\]\[col\];  
if (half == 0) \{  
int re = count;  
if (!flag\[0\]\[0\]) \{  
re = n \* m - re;  
if (re < result)  
result = re;  
\} else if (flag\[0\]\[0\]) \{  
if (re < result)  
result = re;  
\}  
\} else \{  
for (int i = 0; i < 4; i++) \{  
int xx = row + x\[i\];  
int yy = col + y\[i\];  
if (check(xx, yy)) \{  
continue;  
\}  
dfs(xx, yy, count + 1);  
\}  
\}  
flag\[row\]\[col\] = false;  
half += arr\[row\]\[col\];  
  
  
\}  
  
  
private static boolean check(int xx, int yy) \{  
return xx < 0 || xx >= n || yy < 0 || yy >= m || flag\[xx\]\[yy\]  
|| half - arr\[xx\]\[yy\] < 0;  
\}  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关【蓝桥杯】PREV-4 剪格子搜索

资源限制时间限制：1.0s 内存限制：256.0MB 问题描述如下图所示，3 x 3 的格子中填写了一些整数。 ±-–±-+ |10 1|52| ±-

Myth丶恋晨/ 2022年12月15日 12:49/ 0 赞/ 118 阅读

相关试题历届试题剪格子（c++）

dfs（x, y, \_ans, \_sum）朝四个方向递归然后不行就回溯下面是两份代码，最下面那份带了注释，自行观看 include <iostream

柔光的暖阳◎/ 2022年12月12日 04:57/ 0 赞/ 235 阅读

相关试题历届试题剪格子（C++）

include <iostream> using namespace std; const int INF = 1 << 30; in

骑猪看日落/ 2022年12月11日 15:18/ 0 赞/ 222 阅读

相关蓝桥杯剪格子（python实现）

在b站看了大佬的讲解视频，觉得比较好理解，然后将它转换成了python可运行的代码传送门[https://www.bilibili.com/video/BV1Ei4y187

向右看齐/ 2022年11月12日 09:48/ 0 赞/ 161 阅读

相关剪格子

如图p1.jpg所示，3 x 3的格子中填写了一些整数。 ![20150523173639526][] ![Image 1][] 我们沿着图中的红色线剪开，

╰半橙微兮°/ 2022年08月08日 13:58/ 0 赞/ 187 阅读

相关剪格子

如下图所示，3 x 3 的格子中填写了一些整数。 \+–\–+–+ |10\ 1|52| \+–\\–+ |20|30\ 1| \–+ | 1| 2| 3

电玩女神/ 2022年07月24日 06:11/ 0 赞/ 179 阅读

相关剪格子

package 搜索; import java.util.Scanner; public class 剪格子 \{ static int a

逃离我推掉我的手/ 2022年07月12日 12:12/ 0 赞/ 200 阅读

相关历届试题剪格子

问题描述如下图所示，3 x 3 的格子中填写了一些整数。 \+--\--+--+ |10\ 1|52| \+--\\\\--+ |20|30\ 1| \\

心已赠人/ 2022年07月12日 08:22/ 0 赞/ 206 阅读

相关历届试题剪格子

问题描述如下图所示，3 x 3 的格子中填写了一些整数。 ±-–±-+ |10 1|52| ±-\\\–+ |20|30 1| \\\\\\\–+

r囧r小猫/ 2022年03月06日 18:06/ 0 赞/ 233 阅读

相关蓝桥杯剪格子（dfs）

![1613216-20190315000432263-1276307519.png][] include <bits/stdc++.h> usi

我会带着你远行/ 2022年01月12日 12:17/ 0 赞/ 244 阅读