首页 > 代码库 > 放积木

放积木

Description

现有一个n*m的矩阵方格和1*2、2*1两种积木。

矩阵中有些格子是不能放积木的,摆放的积木是不能互相重合的。当然。积木也不能放到矩阵外面。问。这个矩阵,最多能放多少积木?

Input

多组输入。每组第一行有两个整数n、m,表示矩阵有n行。m列。(1<=n,m<=10)
接下来,会有n行字符串。每行有m个字符。

字符仅仅会是‘.’ 或‘*’, ‘*’表示这个格子不能放积木。‘.’表示这个格子能够放积木。

Output

每组输出一行。这行包括一个数字。表示这个矩阵最多放的积木数量。

Sample Input

5 2
.*
..
.*
..
*.

Sample Output

3

代码例如以下:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#define OUT(x) cout << #x << ": " << (x) << endl
using namespace std;
const int mmax=200;
const int inf=0x3fffffff;
bool G[mmax][mmax];
char tt[mmax][mmax];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool vis[mmax];
int link[mmax];
int n,m;
bool find(int x)
{
    

放积木