TIOJ::1073 . B.踩地雷回來了

http://tioj.infor.org/problems/1073

這題感覺上應該是暴搜題。可是很難寫,特例很多,基本上沒玩過踩地雷的應該不會寫|||。
TLE了很久才AC。

題目說了不會有不合法的盤面,所以我們一開始就可以假設盤面都是對的,這樣一來,最自然的作法就是遇到空格就放,或是不放,最後看看合不合法,炸彈是不是放完了。

其中狀況有很多種,所以很麻煩,以每個空格來說,首先就是周為都不是0(可以是 1~8 或是空格或是炸彈),才可以擺炸彈。如果左上角是 1~8 不可以空著(其實算是個小優化,雖然不一定有用XD)。

基本上狀態就切成,可以擺炸彈和不能擺炸彈,還有一種–不知道,因為如果周圍都是還沒翻開的格子,狀態是不確定的

可是如果我們就這樣搜下去絕對會TLE的,於是就要優化啦!我們可以觀察到有很多格子其時是不確定的,對於這些不確定的個子我們可以隨便擺,所以就用排列組合去算就好,如果剩下3個空格要放2顆炸彈,就是 C(3,2)。這樣就可以讓速度快上很多,因為確定的格子不是炸彈就是數字,可能性很少,不確定的格子才是增加遞迴次數的主要原因

然而剩下幾個空格其實很容易錯,基本上因為太複雜了所以我就建表去改囉。當有一個數字變成0的同時,她周圍的不確定格子瞬間都變成一定不是炸彈了,我們要把這些格子去掉,一開始建一個表記錄哪些格子有可能是炸彈,在遞迴的過程中一序拔掉不可能的,注意要記得還原被改過的值,因為 9*9很小所以我在遞迴裡直接開一個陣列保存原本的值。

邊界還有一些狀況要想仔細,到底時,在掃一遍確定每個數字都變成0了,記得還元變數,全域變數和區域變數分清楚,就可以過了。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define XX x+X[i]
#define YY y+Y[i]
using namespace std;
bool SP[10][10];
char D[10][10];
int C[82][82],n,m,cnt,X[8]={-1,-1,-1,0,1,1,1,0},Y[8]={-1,0,1,1,1,0,-1,-1};
bool ck(int x,int y){
return x<0||x>=n||y<0||y>=m;
}
int gg(int x,int y,int t){
if(ck(x,y)||D[x][y]>8)return 0;
D[x][y]+=t;
int tmp=0;
if(D[x][y]==0)F(8)if(!ck(XX,YY)&&SP[XX][YY])tmp++,SP[XX][YY]=false;
return tmp;
}
int DFS(int x,int y,int b,int B){
if(y==m){
if(ck(x-1,y-1)||D[x-1][y-1]>8||D[x-1][y-1]==0)DFS(x+1,0,b,B);
return 0;
}
if(x==n){
// cout<<b<<' '<<B<<endl;
// F(n){Fi(j,m)cout<<(char)(D[i][j]+'0');cout<<endl;}cout<<endl;
F(n)Fi(j,m)if(D[i][j]>0&&D[i][j]<=8)return 0;
return cnt+=C[B][b];
}
if(D[x][y]<=8){
if(ck(x-1,y-1)||D[x-1][y-1]>8||D[x-1][y-1]==0)DFS(x,y+1,b,B);
return 0;
}
bool tag=true,tt=true;
F(8)tag&=ck(XX,YY)||D[XX][YY];
F(8)tt&=ck(XX,YY)||D[XX][YY]>8;
if(tag&&!tt){
int tmp=0;
bool SPB[n][m];
F(n)Fi(j,m)SPB[i][j]=SP[i][j];
F(8)tmp+=gg(XX,YY,-1);
D[x][y]++;
if(ck(x-1,y-1)||D[x-1][y-1]>8||D[x-1][y-1]==0)
if(b>0)DFS(x,y+1,b-1,B-tmp);
D[x][y]--;
F(8)gg(XX,YY,1);
F(n)Fi(j,m)SP[i][j]=SPB[i][j];
}else if(!tag){
bool tmp=SP[x][y];SP[x][y]=false;
if(ck(x-1,y-1)||D[x-1][y-1]>8||D[x-1][y-1]==0)
if(b<=B-tmp)DFS(x,y+1,b,B-tmp);
SP[x][y]=tmp;
}
if(tag&&(ck(x-1,y-1)||D[x-1][y-1]>8))DFS(x,y+1,b,B);
return 0;
}
int main(){
ios_base::sync_with_stdio(false);
C[0][0]=1;
F(81)Fi(j,i+2)C[i+1][j]=C[i][j]+(j?C[i][j-1]:0);
int b,B;
cin>>n;
while(cin>>n>>m>>b){
B=cnt=0;
F(n)cin>>D[i];
F(n)Fi(j,m)D[i][j]-='0',SP[i][j]=D[i][j]>8,B+=SP[i][j];
DFS(0,0,b,B);
cout<<cnt<<endl;
}
}