打卡信奥刷题（3055）用C++实现信奥题 P6757 [BalticOI 2013] Tracks in the Snow

P6757 [BalticOI 2013] Tracks in the Snow题目描述有一个含H HH行W WW列的字符矩阵初始全为.。有两种动物狐狸和兔子将会从左上角走到右下角狐狸会留下F的痕迹兔子会留下R的痕迹。痕迹会相互覆盖。走路规则如下可以往返走不可以走对角线不可以跳格子不可能有两只动物一起走。现在您得到了这个被动物们走过的矩阵请求出至少有几个动物走过了该矩阵。输入格式第一行为两个整数H , W H,WH,W。接下来H HH行一行W WW个字符表示整个字符矩阵。输出格式仅一行一个整数表示至少有几个动物走过了该矩阵。输入输出样例 #1输入 #15 8 FFR..... .FRRR... .FFFFF.. ..RRRFFR .....FFF输出 #12说明/提示数据范围及限制对于30 3030分的数据保证答案≤ 200 \le 200≤200H , W ≤ 500 H,W\le 500H,W≤500。对于100 % 100\%100%的数据保证1 ≤ H , W ≤ 4 × 10 3 1\le H,W\le 4\times 10^31≤H,W≤4×103答案≥ 1 \ge 1≥1读入的字符只会是.或R或F。说明本题译自 Baltic Olympiad in Informatics 2013 Day 2 T2 Tracks in the Snow。C实现#includebits/stdc.husingnamespacestd;#definechg(x)(xR?F:R)//宏定义便于在填充时进行取反chara[4010][4010];intn,m;intfilled;//记录每次填充的面积intnow;//记录当前填充的面积intans;//结果即需要填充的次数voiddfs(intx,inty,chartp){//洪水填充if(a[x][y]!tp)return;if(x0||xn1||y0||ym1)return;//判边界a[x][y]chg(tp);//取反filled;//填充时记录一次dfs(x1,y,tp);dfs(x-1,y,tp);dfs(x,y1,tp);dfs(x,y-1,tp);}signedmain(){cinnm;for(inti1;in;i)cina[i]1;do{nowfilled;filled0;dfs(1,1,a[1][1]);ans;}while(fillednow);//验证是否与上一次重合如果是则跳出循环coutans-1;//由于需要多花一次填充来判断是否结束所以输出时应减一return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容