dfs + 二维数组

大家注意了，这篇题解可能会很详细

分析一下题目，这一题看见题目内容后就知道是一道dfs问题。

需要的变量：一个alcnt代表路径的个数 + 一个mp二维char数组记录RB + 一个dfs函数 + r,c代表矩阵的长和宽

接下来剖析一下dfs的具体实现：
首先，要给出dfs的终止条件，就是两个s_x,s_y指针都到达了矩阵的右下脚，终止后要将alcnt+1
实现代码如下

if(s_x==r and s_y==c){
		++alcnt;
		return ;
	} 

接下来，如果没有结束dfs,那么就循环i从s_x+1,j从s_y+1开始，遍历每个点，如果这个点没有，就不会采纳
同时，题目说明了，要两点变化时颜色不一样，所以要加上一层if判断
接下来是整个的dfs模块实现的代码

if(s_x==r and s_y==c){
		++alcnt;
		return ;
	} 
	else{
		for(int i=s_x+1;i<=r;i++){
			for(int j=s_y+1;j<=c;j++){
				if(mp[i][j]!=s_c){
					dfs(i,j,mp[i][j]);
				}
			}
		}
	}
	return ;

接下来主函数内的就十分简单了，直接dfs(1,1,mp[1][1])，最后输出alcnt即可
整体代码：

#include<bits/stdc++.h>
using namespace std;

int alcnt,r,c;
char mp[19][19];

void dfs(int s_x,int s_y,char s_c){
	if(s_x==r and s_y==c){
		++alcnt;
		return ;
	} 
	else{
		for(int i=s_x+1;i<=r;i++){
			for(int j=s_y+1;j<=c;j++){
				if(mp[i][j]!=s_c){
					dfs(i,j,mp[i][j]);
				}
			}
		}
	}
	return ;
}
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++){
    	for(int j=1;j<=c;j++){
    		cin>>mp[i][j];
		}
	}
    dfs(1,1,mp[1][1]);
    cout<<alcnt;
    return 0;
}