1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;
class Point{ int x, y; public Point(int _x, int _y) { x = _x; y = _y; } }
public class Main { public static int[][] vis = new int[30][30], vis2 = new int[30][30]; public static int[][] arr; public static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; public static int sum = 0, minCnt = 1000, m, n; public static void Update() { int cnt = 0, curSum = 0; for(int i = 0; i < 2 * n + 1; i++) { for(int j = 0; j < 2 * m + 1; j++) { vis2[i][j] = 0; } } Queue<Point>queue = new LinkedList<>(); queue.add(new Point(1, 1)); vis2[1][1] = 1; curSum += arr[1][1]; cnt = 1; while(!queue.isEmpty()) { Point cur = queue.poll(); for(int i = 0; i < 4; i++) { int newX = cur.x + dir[i][0]; int newY = cur.y + dir[i][1]; if(newX >= 0 && newX < 2 * n + 1 && newY >= 0 && newY < 2 * m + 1 && vis2[newX][newY] == 0 && vis[newX][newY] == 0) { queue.add(new Point(newX, newY)); vis2[newX][newY] = 1; curSum += arr[newX][newY]; if(curSum * 2 > sum) return ; if(arr[newX][newY] != 0) cnt++; } } } if(curSum * 2 == sum) minCnt = Math.min(minCnt, cnt); }
public static void dfs(int x, int y) { for(int i = 0; i < 4; i++) { int newX = x + dir[i][0]; int newY = y + dir[i][1]; if(newX >= 0 && newX < 2 * n + 1 && newY >= 0 && newY < 2 * m + 1 && vis[newX][newY] == 0) { if(arr[newX][newY] == 0) { vis[newX][newY] = 1; dfs(newX, newY); vis[newX][newY] = 0; } else Update(); } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); m = sc.nextInt(); n =sc.nextInt(); arr = new int[n * 2 + 1][m * 2 + 1];
for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { arr[i * 2 + 1][j * 2 + 1] = sc.nextInt(); sum += arr[i * 2 + 1][j * 2 + 1]; } }
if(sum % 2 == 1) { System.out.print(0); } else { vis[0][0] = 1; dfs(0, 0); if(minCnt == 1000) System.out.print(0); else System.out.print(minCnt); } sc.close(); }
}
|