解题思路:
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; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:381 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:618 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:542 |
printf基础练习2 (C语言代码)浏览:685 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:669 |
罗列完美数 (C语言代码)浏览:510 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:1022 |
JAM计数法 (C语言代码)浏览:715 |
小O的图案 (C语言代码)浏览:967 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:626 |