2017新鲜面经

roommate

7 X7 |8 E, n" {5 J3 j) o8 ?3 ?
Random generate a NxN matrix with only four types of  element: 1,2,3,4.
2 b$ I/ E& O: k! O. t8 tHowever, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)

0 z/ S) r( X* Tex:

# X5 u7 b' @7 X7 w# Y' O% Nvalid:
1 2 1 1
4 v" [% d. o( }: H) B# v$ n- e3 1 4 2
1 2 4 2
3 1 2 3
& ~! p: T' K" ~% g
invalid because the first column has element 1 appears three times and all 1s are connected to each other :
6 n! l* c8 j2 r0 L( i* P. L
1 2 1 3
1 3 4 2
! l6 r# t: I% S% r4 p1 2 4 4
7 E- W3 f' m. S% `2 s& o2 3 2 2

完美世界

I post my solution below:

import java.util.Random;

# {+ H- w+ r8 ~$ ]public class candyCrush {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
  h4 A- Y4 b4 B9 A& h( i		int[][] res = generateRandon(6);
1 {/ f+ B2 Y% l2 f  Y		for (int i = 0; i < res.length; i++) {
$ [9 s( h/ r  R! S# I			for (int j = 0; j < res[0].length; j++) {
				System.out.print(res[i][j]);
			}
			System.out.println();
		}

	}
8 v& [# h6 I! h$ N& D7 f
, W9 r. G7 K$ H) u	public static int[][] generateRandon(int size) {
' f. [8 t. h$ i2 w$ i		Random r = new Random();
		int dp[][] = new int[size][size];
		for (int x = 0; x < size; x++) {
" v2 l8 _* n9 R% p			for (int y = 0; y < size; y++) {
				int rand = r.nextInt(4) + 1; 
. ]3 g" {+ X7 b% S. p9 J: G  q				if (x > 1 && y > 1) {
					int a = dp[x - 1][y];
# H. R/ D. t, [3 f: e					int b = dp[x][y - 1];
- C4 U  S- q- n					int c = dp[x - 2][y];
' k7 m4 v4 w' o( K					int d = dp[x][y - 2];
					int newRand = rand;
) m6 d. G& Y  h( w: e1 m					if (rand == a && rand == c && b!=d) {
						newRand = a;
* d. D! F  l' S4 D9 {						while (newRand == a) {
							newRand = r.nextInt(4) + 1;
						}
1 h! k0 \) K0 t' g% w9 J# V					}else if (rand == b && rand == d && a!=c) {
0 C2 M/ N3 K, Y2 V, v						newRand = b;
						while (newRand == b) {
0 S4 O( }+ D# q2 o1 b' z							newRand = r.nextInt(4) + 1;
						}
& R- E: u  e/ h					}else if(a==c && b==d){
+ u. }, M( S$ a9 Q% ?						
. ^% P. l8 J$ i! Y& K1 Q						while (newRand == a||newRand==b) {
							newRand = r.nextInt(4) + 1;
						}
& B0 _7 ~2 x* Q- g$ {					}
					
					dp[x][y] = newRand;

				} else if (x <= 1 && y > 1) {
7 ?* X9 m  h* h  n1 n					int a = dp[x][y - 1];
					int b = dp[x][y - 2];
) c# ^) {: @' U# A					int newRand = rand;
					if (rand == a && rand == b) {
						newRand = a;
						while (newRand == a) {
							newRand = r.nextInt(4) + 1;
						}
% _  k/ t6 j2 _8 Y* L, O) M					}
3 _4 A; W2 d  C1 @3 k* G- c					dp[x][y] = newRand;
  V7 c5 E0 V4 j7 }$ D5 s				} else if (y <= 1 && x > 1) {
2 p8 p: z  X2 g7 I) j: V" u					int a = dp[x - 1][y];
					int b = dp[x - 2][y];
1 G' k, _( O+ B( ?& J/ }4 v, i					int newRand = rand;
					if (rand == a && rand == b) {
						newRand = a;
8 _/ S$ Q' P7 V# z						while (newRand == a) {
							newRand = r.nextInt(4) + 1;
% w0 a4 Q* T" P9 M						}
" P& f1 v4 z! q/ L) O; r					}
					dp[x][y] = newRand;
! u6 h! f7 I  v6 e9 ~' R				}else{
  b" b" T" w- l4 W					dp[x][y] = rand;
) y/ T% Z/ I9 T. y, ^				}
			}
		}
		return dp;
: \& h' O$ Y% A, {8 Y	}
) p: C# U3 }; @
; w9 e: t3 {9 F$ x1 d+ [5 q" @}

FbGoo

your solution doesn't allow the case that two elements of same type are next to each other in a row or column, but actually it is allowed. Only three or above connected elements in the same row or column are prohibited.