1837: 蓝桥杯2015年第六届真题-机器人塔 C++代码 常规dfs爆搜

解题思路:

        m和n不大于500，即m+n <= 1000，所以最多不会超过50行。

        定义dfs为 当前访问第i行第j个,需要输入的字符是c，由于定义是访问时输入，因此需要在之前进行计数+1，并判断是否合法。然后第一行和每行最后一个进行特判。

注意事项:
        先判断再递归

        注意搜索失败和完成搜索时候A,B计数器回溯
参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 50;
char Map[N][N];
int countA = 0;
int countB = 0;
int m,n;
int counts = 0;
int dfs(int i,int j,char c){//当前访问第i行第j个,需要输入的字符是c 
	c == 'A'?countA++:countB++;
	Map[i][j] = c;
	if(countA > m || countB > n){
		c == 'A'?countA--:countB--;
		return 0;
	}
	if(countA == m && countB == n){
		c == 'A'?countA--:countB--;
		counts++;
		return 0;
	}
	
	if(i == 1 && j == 1){
		dfs(2,1,'A');
		dfs(2,1,'B');
	}else if(i == j){
		dfs(i+1,1,'A');
		dfs(i+1,1,'B');
	}else{
		if(Map[i-1][j] == 'A' && Map[i][j] == 'A'){
			dfs(i,j+1,'A');
		}else if(Map[i-1][j] == 'A' && Map[i][j]=='B'){
			dfs(i,j+1,'B');
		}else if(Map[i-1][j] == 'B' && Map[i][j] == 'A'){
			dfs(i,j+1,'B');
		}else if(Map[i-1][j] == 'B' && Map[i][j] == 'B'){
			dfs(i,j+1,'A');
		}
	}
	c == 'A'?countA--:countB--;
	return 0;
}
int main(){
	cin>>m>>n;
	dfs(1,1,'A');
	dfs(1,1,'B');
	cout<<counts;
}