c++ 让高桥高兴 如果高桥经过的格子(包括起点和终点)中的数互不相同,高桥就会高兴。问有多少种可以让高桥高兴的路线?
时间: 2024-05-16 22:18:22 浏览: 9
这道题可以使用回溯法来解决。
首先,读入矩阵的大小和矩阵本身,然后从每个格子出发,采用深度优先搜索,不断地寻找下一个可以行走的格子,直到到达终点或者无法继续行走为止。在搜索过程中,需要记录已经经过的数字,如果下一个格子中的数字已经被经过了,则不能继续走。
最后统计所有符合要求的路径数量即可。
下面是 C++ 代码实现:
```c++
#include<iostream>
using namespace std;
const int N=7;
int a[N][N];
bool used[10];
int ans=0;
void dfs(int x,int y,int step){
if(x==N-1&&y==N-1){
ans++;
return;
}
if(x<0||x>=N||y<0||y>=N||used[a[x][y]])
return;
used[a[x][y]]=true;
dfs(x+1,y,step+1);
dfs(x-1,y,step+1);
dfs(x,y+1,step+1);
dfs(x,y-1,step+1);
used[a[x][y]]=false;
}
int main(){
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
cin>>a[i][j];
dfs(0,0,0);
cout<<ans<<endl;
return 0;
}
```
需要注意的是,由于矩阵大小最大只有 $7\times 7$,因此可以直接使用递归实现深度优先搜索,不需要使用栈或队列等数据结构。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)