蓝桥杯历年试题【剪格子】

• 提示：这里的行列数的输入是颠倒的
• 系统的测试样例是有问题的，以下代码明明有问题，却AC了

import java.util.Scanner;
public class Main {
	static int [][]next={{0,1},{0,-1},{1,0},{-1,0}};
	static int n,m,count=100,result=0;
	public static void main(String []args){
		Scanner in=new Scanner(System.in);
		m=in.nextInt();
		n=in.nextInt();
		int [][]excel=new int[n][m];
		int [][]mark=new int[n][m];
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				mark[i][j]=0;
				excel[i][j]=in.nextInt();
				result+=excel[i][j];
			}
		}
		if(result%2!=0){
			System.out.println("0");
			System.exit(0);
		}
		mark[0][0]=1;
		dfs(0,0,excel,mark,1,excel[0][0]);
		if(count==100){
			System.out.println("0");
		}
		else{
			System.out.println(count);
		}
	}
	public static void dfs(int x,int y,int [][]excel,int [][]mark,int cot,int ans){
		for(int i=0;i<4;i++){
			if(ans==result/2){
				if(count>cot){
					count=cot;
				}
			}
			int tx=next[i][0]+x;
			int ty=next[i][1]+y;
			if(tx>=0&&tx<n&&ty>=0&&ty<m&&mark[tx][ty]==0&&ans+excel[tx][ty]<=result/2){
				mark[tx][ty]=1;
				dfs(tx,ty,excel,mark,cot+1,ans+excel[tx][ty]);
				mark[tx][ty]=0;
			}
		}
	}
}

我的代码有两个样例是错误的

1. 3 3
   1 1 1
   1 2 1
   3 1 3

正确答案应该是4个即1，1，2，3。可是运行结果是5个，1，1，1，1，3。

• 这是因为深搜是一条路走到黑的，它从一个点出发，就只能从最外面那个点的方向走，不会改点
• 因此，要有改变方向的一步，让它可以有新的发现

1. 3 3
   10 11 1
   1 1 1
   3 3 9

这里输出的答案是7个，10，1，3，3，1，1，1。其实，这样就分为三块了，故此题应该输出0

• 这是因为在深搜中，它只能保证是不是一条路有顺序的通畅的，并不管分成几块

import java.util.Scanner;
public class Main {
	static int [][]next={{0,1},{0,-1},{1,0},{-1,0},{1,-1}};
	static int n,m,count=100,result=0;
	//static int []record=new int[100];
	static int [][]mark=new int[10][10];
	public static void main(String []args){
		Scanner in=new Scanner(System.in);
		m=in.nextInt();
		n=in.nextInt();
		int [][]excel=new int[n][m];
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				mark[i][j]=0;
				excel[i][j]=in.nextInt();
				result+=excel[i][j];
			}
		}
		if(result%2!=0){
			System.out.println("0");
			System.exit(0);
		}
		mark[0][0]=1;
		dfs(0,0,excel,1,excel[0][0]);
		if(count==100){
			System.out.println("0");
		}
		else{
			System.out.println(count);
		}
	}
	public static boolean block(int cot){
		int blocks=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(mark[i][j]==0){
					blocks++;
					if((i+1<n&&mark[i+1][j]==0)||(i-1>=0&&mark[i-1][j]==0)||(j-1>=0&&mark[i][j-1]==0)||(j+1<m&&mark[i][j+1]==0)){
						continue;
					}
					else{
						return m*n-cot==blocks? true:false;
					}
				}
			}
		}
		return true;
	}
	public static void dfs(int x,int y,int [][]excel,int cot,int ans){
		for(int i=0;i<5;i++){
			if(ans==result/2){
				if(count>cot&&block(cot)){
					count=cot;
				}
				/*System.out.println(cot);
				for(int j=1;j<cot;j++){
					System.out.print(record[j]);
				}*/
			}
			int tx=next[i][0]+x;
			int ty=next[i][1]+y;
			if(tx>=0&&tx<n&&ty>=0&&ty<m&&mark[tx][ty]==0&&ans+excel[tx][ty]<=result/2){
				mark[tx][ty]=1;
				//record[cot]=excel[tx][ty];
				dfs(tx,ty,excel,cot+1,ans+excel[tx][ty]);
				mark[tx][ty]=0;
			}
		}
	}
}