本文主要是介绍放积木，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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)
{
for(int i=1;i<=n*m;i++)
{
if(G[x][i] && !vis[i])
{
vis[i]=true;
if(link[i]==0 || find(link[i]))
{
link[i]=x;
return true;
}
}
}
return false;
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(G,false,sizeof G);
for(int i=0;i<n;i++)
scanf("%s",tt[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(tt[i][j]=='.')
for(int e=0;e<4;e++)
{
int ni=i+dir[e][0];
int nj=j+dir[e][1];
if(ni>=0 && ni<n && nj>=0 && nj<m && tt[ni][nj]=='.')
G[i*m+j+1][ni*m+nj+1]=1;
}
}
}
int cnt=0;
memset(link,0,sizeof link);
for(int i=0;i<=n*m;i++)
{
memset(vis,false,sizeof vis);
if(find(i))
cnt++;
}
printf("%d\n",cnt/2);
}
return 0;
}
更多做题心得的详情请查看（记得关注哦）https://mp.weixin.qq.com/s?__biz=MzIyOTM4MDMxNw==&mid=2247483798&idx=1&sn=d4fbd34e50ce4efda39d7710d2dc5dc9&chksm=e842d824df3551320d7f1ed85286b2616aec419f7a852cc5c9c9f270beb237b5e6ca83166162&token=1630951018&lang=zh_CN#rd
|
这篇关于放积木的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
