深信服笔试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;
}