-

#include<assert.h>
#include<time.h>
#include<stdio.h>
#define rep(i,l,r) for(int i=(l);i<(r);i++)
#define isinboard(x,y) ((1<=x&&x<=W)&&(1<=y&&y<=H))
#define iskinbou(x,y,xx,yy) ((x==xx-1||x==xx||x==xx+1)&&(y==yy-1||y==yy||y==yy+1))
#define isnum(x,y) (check[x][y]&&!bomb[x][y])
#define unopenkinbou(x,y) rep(i,0,3)rep(j,0,3)if(isinboard(x+i-1,y+j-1)&&!check[x+i-1][y+j-1])
#define W 30
#define H 16
#define B 99
#define ATTEMPT 10000


//1-based index
int bomb[W+2][H+2];//地雷なら1、非地雷なら0
int num[W+2][H+2];//非地雷なら近傍の地雷の個数、地雷なら適当な値(1000以上)
int check[W+2][H+2];//開拓済みor地雷確定済みなら1、そうでないなら0
int cnt;//まだ開かれていない非地雷マスの数

//盤面の出力（デバッグ用）
void printboard(int a,int b){
	rep(y,1,H+1){
		rep(x,1,W+1){
			if(x==a&&y==b)printf("★");
			else if(!check[x][y])printf("□");
			else if(bomb[x][y])printf("■");
			else switch(num[x][y]){
				case 0:printf("０");break;
				case 1:printf("１");break;
				case 2:printf("２");break;
				case 3:printf("３");break;
				case 4:printf("４");break;
				case 5:printf("５");break;
				case 6:printf("６");break;
				case 7:printf("７");break;
				case 8:printf("８");break;
			}
		}
//		rep(x,1,W+1)printf("%d",check[x][y]);
		puts("");
	}
	puts("");
}

//乱数(xoroshiro128)
unsigned long long xorshiro[2]={0xcbe134025aac2d13,0x9e30d9a3f85a62c7};//適当な初期値
unsigned long long rand(){
	unsigned long long s0=xorshiro[0],s1=xorshiro[1];
	s1^=s0;
	xorshiro[0]=((s0<<55)|(s0>> 9))^s1^(s1<<14);
	xorshiro[1]=((s1<<36)|(s1>>28));
	return xorshiro[0]+xorshiro[1];
}

//(sx,sy)がopsとなる盤面を生成
void makeboard(int sx,int sy){
	//初期化
	rep(i,1,W+1)rep(j,1,H+1)bomb[i][j]=num[i][j]=check[i][j]=0;
	cnt=H*W-B;
	
	int rest=B;
	while(rest){
		int x=rand()%W+1,y=rand()%H+1;
		if(!bomb[x][y]&&!iskinbou(x,y,sx,sy)){
			bomb[x][y]=1;
			num[x][y]=1000;
			rep(i,0,3)rep(j,0,3)if(!(i==1&&j==1))num[x+i-1][y+j-1]++;
			rest--;
		}
	}
	rep(i,0,W+2)check[i][0]=check[i][H+1]=1;
	rep(j,0,H+2)check[0][j]=check[W+1][j]=1;
}

//solver本体
int solve(){
	while(cnt){
		int flag=1;
		//single
		while(flag){
			flag=0;
			rep(x,1,W+1)rep(y,1,H+1)if(isnum(x,y)){
				//未確定が1属性なら全部決まる
				int ok=0,ng=0;
				unopenkinbou(x,y){
					if(bomb[x+i-1][y+j-1])ng++;
					else ok++;
				}
				if(ok==0^ng==0){
					unopenkinbou(x,y){
						check[x+i-1][y+j-1]=1;
						if(!bomb[x+i-1][y+j-1])cnt--;						
						flag=1;
					}
				}
			}
		}
		//pair
		rep(x,1,W+1)rep(y,1,H+1)if(isnum(x,y)){
			rep(jj,0,3)rep(ii,(jj?0:3),5){
				int xx=x+ii-2,yy=y+jj;
				if(isinboard(xx,yy)&&isnum(xx,yy)){
					//(x,y)の近傍のみに含まれるものと(xx,yy)の近傍のみに含まれるものがそれぞれ1属性かつ異なるなら開く
					
					//(x,y)の近傍をチェック
					int ok=0,ng=0;
					unopenkinbou(x,y){
						if(bomb[x+i-1][y+j-1])ng++;
						else ok++;
					}
					//(xx,yy)の近傍をチェック
					int xxok=0,xxng=0;
					unopenkinbou(xx,yy){
						if(iskinbou(x,y,xx+i-1,yy+j-1)){//共通の近傍
							if(bomb[xx+i-1][yy+j-1])ng--;
							else ok--;
						}else{
							if(bomb[xx+i-1][yy+j-1])xxng++;
							else xxok++;
						}
					}
					
					if((ok==0||ng==0)&&(xxok==0||xxng==0)&&(ok||ng||xxok||xxng)&&((ok==0&&xxng==0)||(ng==0&&xxok==0))){
//						printf("(%d,%d) (%d,%d) %d %d %d %d\n",x,y,xx,yy,ok,ng,xxok,xxng);
//						printboard(-1,-1);
						rep(nnn,0,2){
							unopenkinbou(xx,yy){
								if(!iskinbou(x,y,xx+i-1,yy+j-1)){//共通の近傍でない
//									printf("%d %d\n",xx+i-1,yy+j-1);
									check[xx+i-1][yy+j-1]=1;
									if(!bomb[xx+i-1][yy+j-1])cnt--;
									flag=1;
								}
							}
							int t;
							t=x;x=xx;xx=t;
							t=y;y=yy;yy=t;
						}
					}
				}
			}
		}
		
		//random
		while(flag==0&&cnt>0){
			int x=rand()%W+1,y=rand()%H+1;
//			printboard(x,y);
			if(!check[x][y]){
				if(bomb[x][y]){
					return 0;
				}
				check[x][y]=1;
				cnt--;
				break;
			}
		}
	}
//	printf("ok\n");
	return 1;
}

int main(){
	assert(H*W>=B+9);
	int ans=0;
	clock_t start=clock();
	rep(n,0,ATTEMPT){
		//初期化
		int x=rand()%W+1,y=rand()%H+1;
		makeboard(x,y);
		check[x][y]=1;
		cnt--;
		if(solve())ans++;
	}
	printf("%d/%d\n",ans,ATTEMPT);
	printf("%.3f秒\n",(double)(clock()-start)/CLOCKS_PER_SEC);
}