打卡信奥刷题（2994）用C++实现信奥题 P6131 [USACO11NOV] Cow Beauty Pageant S

P6131 [USACO11NOV] Cow Beauty Pageant S题目描述听说最近流行表皮有三个斑点的奶牛Farmer John 迅速购买了不少这样的奶牛。但流行趋势也在改变最近改为流行只有一个斑点的奶牛了。FJ 决定在他的奶牛上涂色从而把三个斑点合并成一个。牛皮由一个N×MN \times MN×M的矩阵来表示像这样................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... ..XXX....XXX....每个X表示斑点的一部分。如果两个X在竖直或水平方向上相邻则它们属于同一个斑点对角线相邻不算。因此上面表示的是一头具有三个斑点的奶牛。FJ 可以通过将一些.涂成X来改变牛身上的图案。他希望使用尽可能少的涂料将三个斑点合并为一个斑点。对于上图下面是一种消耗涂料最少的方案只涂了 4 个格子新涂的格将用*表示................ ..XXXX....XXX... ...XXXX*...XX... .XXXX..**..XXX.. ...*....XXXXX... ..XXX....XXX....现在请你帮 FJ 算出将三个斑点合并为一个斑点最少需要涂多少格子。输入格式第一行两个整数N,MN,MN,M1≤N,M≤501 \leq N,M \leq 501≤N,M≤50。接下来NNN行每行MMM个字符.或X描述牛表皮的斑点分布情况。保证这头牛恰好有三个斑点。输出格式输出将三个斑点合并为一个斑点最少需要涂多少格子。输入输出样例 #1输入 #16 16 ................ ..XXXX....XXX... ...XXXX....XX... .XXXX......XXX.. ........XXXXX... ..XXX....XXX....输出 #14C实现#includebits/stdc.husingnamespacestd;intcol0;intn,m;string s[55];intid[55][55];intdis[5][5];intdisP[5][55][55];voiddfs(intx,inty){if(xn||x1||ym||y1)return;if(s[x][y].)return;if(id[x][y]0)return;id[x][y]col;dfs(x1,y);dfs(x,y1);dfs(x-1,y);dfs(x,y-1);}intmain(){cinnm;for(inti1;in;i){cins[i];s[i] s[i];}for(inti1;in;i)for(intj1;jm;j)if(id[i][j]0s[i][j]X){col;dfs(i,j);}memset(dis,999999,sizeof(dis));memset(disP,999999,sizeof(disP));for(inti1;in;i)for(intj1;jm;j)for(intx1;xn;x)for(inty1;ym;y){if(id[i][j]0id[x][y]0id[i][j]!id[x][y])dis[id[i][j]][id[x][y]]min(dis[id[i][j]][id[x][y]],abs(i-x)abs(j-y));elseif(id[i][j]0id[x][y]0)disP[id[x][y]][i][j]min(disP[id[x][y]][i][j],abs(i-x)abs(j-y));elsecontinue;}intansmin(dis[2][3]dis[1][3],min(dis[1][2]dis[1][3],dis[1][2]dis[2][3]))-2;for(inti1;in;i)for(intj1;jm;j)if(id[i][j]0)ansmin(ans,disP[1][i][j]disP[2][i][j]disP[3][i][j]-2);coutansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容