首页 > 深信服笔试09.10 第二题个人解法
头像
kill_LB
编辑于 2020-09-10 22:04
+ 关注

深信服笔试09.10 第二题个人解法

矩形区域,排布x*y的房间,每个房间与上下左右四个房间相连通,,每个房间有不同的蔬果,此时有一只小白鼠,从某房间进入,去吃每个房间的果蔬,最终从某个房间离开,要求吃到所有的水果,并且每个房间只能进入一次,问老鼠有多少种走法?(即为:指定起点终点,经过所有的点的路径数,各个点不能重复走过)
#include <iostream>
#include <vector>
int ans  =0;

int tar = 0;
using namespace std;
class solu{
public:
int uni(vector<vector<int>> & g){
for(int i = 0;i<g.size();i++){
for(int j = 0; j<g[0].size();j++){
if(g[i][j]==0)
tar++;//统计可以走过的房间数
}
}
for(int i = 0;i<g.size();i++){
for(int j = 0; j<g[0].size();j++){
if(g[i][j]==1){
vector<vector<bool>>  vi (g.size(),vector<bool>(g[0].size(),false));
dfs(g,i,j,vi,0);
}
}
}
return ans;
}
void  dfs (vector<vector<int>> & g, int i,int j,vector<vector<bool>> vi,int num){
vi[i][j] = true;
if(g[i][j]==2 && num == tar){
ans++;
//cout<<ans;
return;
}else if(g[i][j] == 2){
return;
}
if(g[i][j] == 0)
num++;
if(i-1>=0 && !vi[i-1][j]&&g[i-1][j]!=-1)
dfs(g,i-1,j,vi,num);
if(i+1<g.size() && !vi[i+1][j]&&g[i+1][j]!=-1)
dfs(g,i+1,j,vi,num);
if(j-1>=0 && !vi[i][j-1] && g[i][j-1]!=-1)
dfs(g,i,j-1,vi,num);
if(j+1<g[0].size() && !vi[i][j+1]&&g[i][j+1]!=-1)
dfs(g,i,j+1,vi,num);

}
};

int main(){
int m,n,d;
cin>>m>>n;
int b[4];
for(int i=0;i<4;i++)
cin>>b[i];
vector <vector <int> > a(m,vector <int>(n,0));
a[b[0]][b[1]]=1;
a[b[2]][b[3]]=2;
solu s;
d=s.uni(a);
cout<<d;
return 0;
}


全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐