Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
3.4 kB
4
Indexable
Never
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max(a, b) ((a > b) ? a : b)

short dp[21][21][21][21][21][21], tet[21];
short n, length, width = 5;

short play(int, int, int, int, int, int);


int main(){

	short t;
	scanf("%hd", &t);
	while(t--){
		scanf("%hd %hd ", &n, &length);
		for(int i=0; i<n; i++) scanf("%hd", &tet[i]);
		memset(dp, -1, sizeof(dp));
		int ans = play(0, 0, 0, 0, 0, 0);
		// printf("ans = %d\n", ans);
		if(ans == n + 1) puts("Win");
		else printf("Lose at %d\n", ans);
	}
	
	return 0 ;
}

short play(int i, int w1, int w2, int w3, int w4, int w5){
	// printf("i = %d, dp = %d\n%d %d %d %d %d\n", i, dp[i][w1][w2][w3][w4][w5], w1, w2, w3, w4, w5);
	if(dp[i][w1][w2][w3][w4][w5] != -1) return dp[i][w1][w2][w3][w4][w5];
	
	if(i >= n) return dp[i][w1][w2][w3][w4][w5] = n + 1; 
	
	int tetro_n = i + 1, tmp;
// stick
	if(tet[i] == 1){
	// 直放
		if(w1 + 4 <= length) tetro_n = max(tetro_n, play(i+1, w1+4, w2, w3, w4, w5));
		if(w2 + 4 <= length) tetro_n = max(tetro_n, play(i+1, w1, w2+4, w3, w4, w5));
		if(w3 + 4 <= length) tetro_n = max(tetro_n, play(i+1, w1, w2, w3+4, w4, w5));
		if(w4 + 4 <= length) tetro_n = max(tetro_n, play(i+1, w1, w2, w3, w4+4, w5));
		if(w5 + 4 <= length) tetro_n = max(tetro_n, play(i+1, w1, w2, w3, w4, w5+4));
	// 橫放
		tmp = max(max(w1, w2), max(w3, w4)) + 1;
		if(tmp <= length) tetro_n = max(tetro_n, play(i+1, tmp, tmp, tmp, tmp, w5));
		tmp = max(max(w5, w2), max(w3, w4)) + 1;
		if(tmp <= length) tetro_n = max(tetro_n, play(i+1, w1, tmp, tmp, tmp, tmp));
	}
// square
	else if(tet[i] == 2){
		
		tmp = max(w1, w2) + 2;
		if(tmp <= length) tetro_n = max(tetro_n, play(i+1, tmp, tmp, w3, w4, w5));
		tmp = max(w2, w3) + 2;
		if(tmp <= length) tetro_n = max(tetro_n, play(i+1, w1, tmp, tmp, w4, w5));
		tmp = max(w3, w4) + 2;
		if(tmp <= length) tetro_n = max(tetro_n, play(i+1, w1, w2, tmp, tmp, w5));
		tmp = max(w4, w5) + 2;
		if(tmp <= length) tetro_n = max(tetro_n, play(i+1, w1, w2, w3, tmp, tmp));
	}
// cross
	else if(tet[i] == 3){						// +1 因為十字往下多一格
		tmp = max(w1, max(w2+1, w3)) + 1;		
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, tmp, tmp+1, tmp, w4, w5));
		tmp = max(w2, max(w3+1, w4)) + 1;
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, w1, tmp, tmp+1, tmp, w5));
		tmp = max(w3, max(w3+1, w5)) + 1;
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, w1, w2, tmp, tmp+1, tmp));
	}
// s
	else if(tet[i] == 4){
	//   _
	// _|
		tmp = max(w1, max(w2, w3-1)) + 1;
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, tmp, tmp+1, tmp+1, w4, w5));
		tmp = max(w2, max(w3, w4-1)) + 1;
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, w1, tmp, tmp+1, tmp+1, w5));
		tmp = max(w3, max(w4, w5-1)) + 1;
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, w1, w2, tmp, tmp+1, tmp+1));
	// |_
	//   |
		tmp = max(w1, w2+1) + 1;
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, tmp+1, tmp, w3, w4, w5));
		tmp = max(w2, w3+1) + 1;
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, w1, tmp+1, tmp, w4, w5));
		tmp = max(w3, w4+1) + 1;
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, w1, w2, tmp+1, tmp, w5));
		tmp = max(w4, w5+1) + 1;
		if(tmp + 1 <= length) tetro_n = max(tetro_n, play(i+1, w1, w2, w3, tmp+1, tmp));
	}

	return dp[i][w1][w2][w3][w4][w5] = tetro_n;
}