深度优先

这个家伙好懒，除了文章什么都没留下

0%

【算法】暗恋（只是标题党）

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

蓝桥杯上的基础练习基本做完了，然后在题库里随便翻了下，发下了这个题，以为是一个程序猿暗恋某某的题，结果点进去才发现这个暗恋有个毛的关系啊。就是求一个最大的正方形。居然是个标题党。还是把它做了，结果只得了80分，一个错误，一个超时的。然后百度了下别人的代码，和我的差不多。但思路清晰些，所以一起贴出来。

算法训练 暗恋
时间限制：1.0s 内存限制：256.0MB

问题描述
同在一个高中，他却不敢去找她，虽然在别人看来，那是再简单不过的事。暗恋，是他唯一能做的事。他只能在每天课间操的时候，望望她的位置，看看她倾心的动作，就够了。操场上的彩砖啊，你们的位置，就是他们能够站立的地方，他俩的关系就像砖与砖之间一样固定，无法动摇。还记得当初铺砖的工人，将整个操场按正方形铺砖（整个操场可视为R行C列的矩阵，矩阵的每个元素为一块正方形砖块），正方形砖块有两种，一种为蓝色，另一种为红色。我们定义他和她之间的“爱情指标”为最大纯色正方形的面积，请你写一个程序求出“爱情指标”。
输入格式
第一行两个正整数R和C。
接下来R行C列描述整个操场，红色砖块用1来表示，蓝色砖块用0来表示。
输出格式
一个数，表示他和她之间的“爱情指标”。
样例输入
5 8
0 0 0 1 1 1 0 1
1 1 0 1 1 1 1 1
0 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0
1 1 1 0 1 1 0 1
样例输出
9
数据规模和约定
40%的数据R,C<=10;
70%的数据R,C<=50;
100%的数据R,C<=200;

自己写的，主要是穷举每个点 

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
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		int c=sc.nextInt();
		int r=sc.nextInt();
		int[][] arr=new int[c][r];
		
		for (int i = 0; i < c; i++) {
			for (int j = 0; j < r; j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		
		int max=1;
		for (int i = 0; i < c; i++) {
			for (int j = 0; j < r; j++) {
				int k=arr[i][j];
				boolean fa=true;
				int bian=1;
				while(fa){

					System.out.println(i+"..."+j);
					if((c<=i+max)&&(r<=j+max)){
						System.out.println(max*max);
						return;
					}
					
					aa:for (int a = i; a <= i+bian&&a<c; a++) {
						for (int b = j; b <= j+bian&&b<r; b++) {
							if(arr[a][b]!=k){
								fa=false;
								break aa;
							}
						}
					}
					if(i!=c-1&&j!=r-1){
						if(fa){
							bian++;
						}
					}else{
						fa=false;
					}
					if(max<bian){
						max=bian;
					}
				}
				System.out.println(bian);
			}
		}
	}
}

别人的分开写，单独写个方法。 

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
import java.util.Scanner;


public class Main{

	static int s[][]=new int[200][200];
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		int r=sc.nextInt();
		int c=sc.nextInt();
		
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				s[i][j]=sc.nextInt();
			}
		}
		int max=1;
		int min=Math.max(r, c);
		
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				
				for (int w = max+1; w <= min; w++) {
					if(i+w<=r && j+w<=c){
						if(ispure(i,j,w)==1) max=w;
					}
					else break;
				}
			}
		}
		System.out.println(max*max);
	}

	private static int ispure(int x, int y, int w) {
		int a=s[x][y];
		for (int i = 0; i < w; i++) {
			for (int j = 0; j < w; j++) {
				if(s[x+i][y+j]!=a) return 0;
			}
		}
		return 1;
	}

}