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

  • 提示:这里的行列数的输入是颠倒的
  • 系统的测试样例是有问题的,以下代码明明有问题,却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;
			}
		}
	}
}

 


版权声明:本文为weatarse原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
THE END
< <上一篇
下一篇>>