网站建设销售话术开场白,做网站应聘平台,网站建设兼职薪酬怎么样,ui设计软件哪个好听说最近两斑点的奶牛最受欢迎#xff0c;约翰立即购进了一批两斑点牛。
不幸的是#xff0c;时尚潮流往往变化很快#xff0c;当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色#xff0c;使得它们身上的两个斑点能够合为一个斑点#xff0c;让它们能够更…听说最近两斑点的奶牛最受欢迎约翰立即购进了一批两斑点牛。
不幸的是时尚潮流往往变化很快当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色使得它们身上的两个斑点能够合为一个斑点让它们能够更加时尚。
牛皮可用一个 N×M 的字符矩阵来表示如下所示
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....其中X 表示斑点部分。
如果两个 X 在垂直或水平方向上相邻对角相邻不算在内则它们属于同一个斑点由此看出上图中恰好有两个斑点。
约翰牛群里所有的牛都有两个斑点。
约翰希望通过使用油漆给奶牛尽可能少的区域内涂色将两个斑点合为一个。
在上面的例子中他只需要给三个 .. 区域内涂色即可新涂色区域用 ∗∗ 表示
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....请帮助约翰确定为了使两个斑点合为一个他需要涂色区域的最少数量。
输入格式
第一行包含两个整数 N和 M。
接下来 N 行每行包含一个长度为 M 的由 X 和 .. 构成的字符串用来表示描述牛皮图案的字符矩阵。
输出格式
输出需要涂色区域的最少数量。
数据范围
1≤N,M≤50
输入样例
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....输出样例
3
听说最近两斑点的奶牛最受欢迎约翰立即购进了一批两斑点牛。
不幸的是时尚潮流往往变化很快当前最受欢迎的牛变成了一斑点牛。
约翰希望通过给每头奶牛涂色使得它们身上的两个斑点能够合为一个斑点让它们能够更加时尚。
牛皮可用一个 N×M× 的字符矩阵来表示如下所示
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....其中X 表示斑点部分。
如果两个 X 在垂直或水平方向上相邻对角相邻不算在内则它们属于同一个斑点由此看出上图中恰好有两个斑点。
约翰牛群里所有的牛都有两个斑点。
约翰希望通过使用油漆给奶牛尽可能少的区域内涂色将两个斑点合为一个。
在上面的例子中他只需要给三个 .. 区域内涂色即可新涂色区域用 ∗∗ 表示
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....请帮助约翰确定为了使两个斑点合为一个他需要涂色区域的最少数量。
输入格式
第一行包含两个整数 N 和 M。
接下来 N 行每行包含一个长度为 M 的由 X 和 .. 构成的字符串用来表示描述牛皮图案的字符矩阵。
输出格式
输出需要涂色区域的最少数量。
数据范围
1≤N,M≤501≤,≤50
输入样例
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....输出样例
3 参考代码
/*
统计两个团的所有点的坐标双重遍历一边利用曼哈顿距离找到两图形中最近的两点的距离
*/
#includeiostream
#includealgorithm
#includevector#define x first
#define y secondusing namespace std;
typedef pairint, int PII;
const int N 55;
vectorPII points[2];
int n,m;
char g[N][N];
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};void dfs(int x,int y,vectorPII ps)
{g[x][y] .;ps.push_back({x,y});for(int i0;i4;i){int a x dx[i] ,b y dy[i];if(g[a][b]X)dfs(a,b,ps);}
}int main()
{cinnm;for(int i0;in;i) cing[i];for(int i0,k0;in;i)for(int j0;jm;j)if(g[i][j]X)dfs(i,j,points[k]);int res 1e9;for(auto a : points[0])for(auto b :points[1])res min(res,abs(a.x-b.x)abs(a.y-b.y)-1);coutres;return 0;
}
