Morris' Blog

2011-09-09 09:54:44Morris

b043. B. 踩地雷回來了

留言 1 收藏 0 推薦 0

內容：

Wow! 還記得那隻會玩踩地雷的牡蠣嗎？玩踩地雷的生活是多采多姿的，很快牡蠣就發現新的問題而牠再次陷入一個困境，於是牠想起了你。(雖然說一個禮拜前你沒能幫上牠，但牠依舊對你抱有希望)

偶然的一個情況下，牡蠣進行到如左圖的盤面，留意到該盤面的右下角有一個2×2的小方形，很明顯地我們無法再利用牡蠣的四種策略進行下去，因為剛好有2種可能的地雷分布而且這兩種都不會使整個盤面已出現的數字造成任何矛盾情形。當然這種情況我們只能把命運交給上帝了。

不過牡蠣馬上聯想到一個問題 (玩踩地雷使牠變成一個好奇寶寶？)，對於隨意給定的一個盤面，這個盤面會有多少種可能(不違背已經被翻開來的數字)的地雷分佈呢？牡蠣將這個問題交給了你。呃，更精確地說是，交給了你的程式。

輸入說明：

輸入檔第一行有一個正整數T (1 ≤ T ≤ 20)，表示接下來有T組踩地雷盤面。每一組盤面的輸入第一行有三個正整數M, N, B (1 ≤ M,N ≤ 9)。表示該盤面的寬為N，高為M，一共有B個炸彈 (1 ≤ B ≤ M×N)。

接下來M行每行包含N個字元，顯示盤面的狀況。字元只有以下幾種可能：

1. 0~8 : 表示該格點已被牡蠣翻開，數字為該格點周圍的地雷總數。

2. ‘_’(不含引號) : 表示該格點尚未被牡蠣翻開。

輸出說明：

對每一組測試資料，輸出一行訊息。該行包含一個整數C，表示該盤面所有可能的地雷分布總數。你可以假設所有測試資料的答案1 ≤ C ≤ 10⁸。也就是說，對每一組踩地雷盤面，可能的地雷分佈不會超過10⁸組解，且至少有一組解。

範例輸入：

範例輸出：

提示：

出處：

2005 NPSC 高中組決賽

作法 : 窮舉+組合

先窮舉符合在數字附近的炸彈, 剩餘的炸彈,
在剩餘炸彈可以都可放置的地方, 做一個數學組合的運算加速

/**********************************************************************************/
/* Problem: b043 "B. 踩地雷回來了" from 2005 NPSC 高中組決賽          */
/* Language: C                                                                   */
/* Result: AC(1.2s, 280KB) judge by this@ZeroJudge                               */
/* Author: morris1028 at 2011-09-09 09:40:06                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
int C[101][101] = {};
int Ans, n, m, B, unknow;
struct {
   int x, y;
}NUM[101];
char map[20][20], set[20][20];
int D[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},
               {0,1},{1,-1},{1,0},{1,1}};
void DFS(int , int);
void PASCAL(int n) {
   int i, j;
   C[0][0] = 1;
   for(i = 1; i <= n; i++) {
       C[i][0] = 1;
       for(j = 1; j <= i; j++)
           C[i][j] = C[i-1][j-1] + C[i-1][j];
   }
}
int Check(int x, int y) {
   static int i, k, tx, ty;
   for(i = 0, k = 0; i < 8; i++) {
       tx = x+D[i][0], ty = y+D[i][1];
       if(tx >= 0 && tx < m && ty >= 0 && ty < n) {
           if(set[tx][ty] == 1)
               k++;
       }
   }
   return k;
}
int Calu_excee(int x, int y) {
   static int i, tx, ty, total;
   for(i = 0; i < 8; i++) {
       tx = x+D[i][0], ty = y+D[i][1];
       if(tx >= 0 && tx < m && ty >= 0 && ty < n && map[tx][ty] != '_') {
           total = Check(tx, ty);
           if(total > map[tx][ty]-'0')
               return 0;
       }
   }
   return 1;
}
int Calu(int Bomb) {
   static int i, j, k, guess, tx, ty, total;
   for(i = 0, guess = 0; i < m; i++)
       for(j = 0; j < n; j++)
           if(map[i][j] == '_' && set[i][j] == 0) {
               set[i][j] = 1;
               if(Calu_excee(i, j) == 1)   {guess++;}
               set[i][j] = 0;
           }
   return C[guess][Bomb];
}
void Backtracking(int x, int y, int num, int Idx, int Bomb, int Midx) {
   if(Midx == 8 && num == 0) {
       DFS(Idx+1, Bomb);
       return;
   }
   if(Midx == 8 || 8-Midx < num)
       return;
   int tx = x+D[Midx][0], ty = y+D[Midx][1];
   if(tx >= 0 && tx < m && ty >=0 && ty < n && map[tx][ty] == '_' && set[tx][ty] == 0) {
       set[tx][ty] = 1;
       if(Calu_excee(tx, ty) == 1)
           Backtracking(x, y, num-1, Idx, Bomb-1, Midx+1);
       set[tx][ty] = 0;
       Backtracking(x, y, num, Idx, Bomb, Midx+1);
   } else {
       Backtracking(x, y, num, Idx, Bomb, Midx+1);
   }
}
void DFS(int Idx, int Bomb) {
   if(Idx == unknow) {
       Ans += Calu(Bomb);
       return;
   }
   int item = Check(NUM[Idx].x, NUM[Idx].y);
   int total = map[NUM[Idx].x][NUM[Idx].y]-'0';
   if(item > total)
       return;
   if(item == total)
       DFS(Idx+1, Bomb);
   if(item < total) {
       Backtracking(NUM[Idx].x, NUM[Idx].y, total - item, Idx, Bomb, 0);
   }
}
main() {
   PASCAL(100);
   int T, i, j, k;
   scanf("%d", &T);
   while(T--) {
       scanf("%d %d %d", &m, &n, &B);
       for(i = 0; i < m; i++)
           scanf("%s", map[i]);
       k = 0;
       for(i = 0; i < m; i++)
           for(j = 0; j < n; j++) {
               if(map[i][j] >= '1' && map[i][j] <= '9')
                   NUM[k].x = i, NUM[k].y = j, k++;
               set[i][j] = 0;
           }
       Ans = 0, unknow = k;
       DFS(0, B);
       printf("%d\n", Ans);
   }
   return 0;
}

上一篇：b069. A. 千里傳情

下一篇：b259. H. 補習班的報名熱