题目描述
现在有一个城市销售经理，需要从公司出发，去拜访市内的商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他只能在左右中选择一个方向，在上下中选择一个方向，现在问他有多少种方案到达商家地址。
给定一个地图map及它的长宽n和m，其中1代表经理位置，2代表商家位置，-1代表不能经过的地区，0代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于10。 测试样例：
[[0,1,0],[2,0,0]],2,3
返回：2
程序代码
方法一：
#include <iostream>
#include <vector>
using namespace std;
void vistMap(vector<vector<int> > map,int startx,int starty,int endx,
int endy,int vistlr,int vistud,int &s){
if(startx==endx&&starty==endy){
s++;
return;
}
int n=map.size()-1;
int m=map[0].size()-1;
if((startx+vistlr>=0)&&(startx+vistlr<=m)){
if(map[starty][startx+vistlr]!=-1)
vistMap(map,startx+vistlr,starty,endx,
endy,vistlr,vistud,s);
}
if((starty+vistud>=0)&&(starty+vistud<=n)){
if(map[starty+vistud][startx]!=-1)
vistMap(map,startx,starty+vistud,endx,
endy,vistlr,vistud,s);
}
}
int countPath(vector<vector<int> > map, int n, int m){
int startx,starty,endx,endy;
for(int i=0;i<map.size();i++){
for(int j=0;j<map[i].size();j++){ //确定经理和商城的位置
if(map[i][j]==1){
startx=j;
starty=i;
}
if(map[i][j]==2){
endx=j;
endy=i;
}
}
}
int vistlr;
if(startx>endx) //确定向左走还是向右走
vistlr=-1;
else if(startx<endx)
vistlr=1;
else
vistlr=0;
int vistud;
if(starty>endy) //确定向上走还是向下走
vistud=-1;
else if(starty<endy)
vistud=1;
else
vistud=0;
int s=0;
vistMap(map,startx,starty,endx,endy,vistlr,vistud,s); //递归遍历
return s;
}
int main(){
int a1[3]={1,0,0};
int a2[3]={-1,0,2};
vector<int> arr1(a1,a1+3);
vector<int> arr2(a2,a2+3);
vector<vector<int> > map;
map.push_back(arr1);
map.push_back(arr2);
int n=2;
int m=3;
int s=countPath(map,n,m);
cout<<s<<endl;
system("pause");
}
方法二：
#include <iostream>
#include <vector>
using namespace std;
struct Point{
int x;
int y;
bool lr;
bool ud;
};
int countPath(vector<vector<int> > map, int n, int m){
int startx,starty,endx,endy;
for(int i=0;i<map.size();i++){
for(int j=0;j<map[i].size();j++){ //确定经理和商城的位置
if(map[i][j]==1){
startx=j;
starty=i;
}
if(map[i][j]==2){
endx=j;
endy=i;
}
}
}
int vistlr;
if(startx>endx) //确定向左走还是向右走
vistlr=-1;
else if(startx<endx)
vistlr=1;
else
vistlr=0;
int vistud;
if(starty>endy) //确定向上走还是向下走
vistud=-1;
else if(starty<endy)
vistud=1;
else
vistud=0;
int sum=0;
vector<Point> path;
Point startp;
startp.x=startx;
startp.y=starty;
startp.lr=true; //标志左右方向没有访问
startp.ud=true; //标志上下方向没有访问
path.push_back(startp);
while(!path.empty()){
int s=path.size()-1;
if(path[s].lr==true){ //左右方向能访问
path[s].lr=false;
int xx=path[s].x+vistlr;
if(xx==endx&&path[s].y==endy){ //是否到达终点
sum++;
path.pop_back(); //出栈
}else{
if(xx>=0&&xx<=m-1){ //判断是否越界
if(map[path[s].y][xx]!=-1){ //判断是否等于-1
Point pointemp;
pointemp.x=xx;
pointemp.y=path[s].y;
pointemp.lr=true;
pointemp.ud=true;
path.push_back(pointemp);
}
}
}
}else if(path[s].lr==false&&path[s].ud==true){ //上下方向能访问
path[s].ud=false;
int yy=path[s].y+vistud;
if(yy==endy&&path[s].x==endx){ //到达终点
sum++;
path.pop_back();
}else{
if(yy>=0&&yy<=n-1){ //判断是否越界
if(map[yy][path[s].x]!=-1){ //判断是否等于-1
Point pointemp;
pointemp.x=path[s].x;
pointemp.y=yy;
pointemp.lr=true;
pointemp.ud=true;
path.push_back(pointemp);
}
}
}
}else{
path.pop_back(); //出栈
}
}
return sum;
}
int main(){
int a1[3]={1,0,-1};
int a2[3]={0,0,0};
int a3[3]={0,0,2};
vector<int> arr1(a1,a1+3);
vector<int> arr2(a2,a2+3);
vector<int> arr3(a3,a3+3);
vector<vector<int> > map;
map.push_back(arr1);
map.push_back(arr2);
map.push_back(arr3);
int n=3;
int m=3;
int s=countPath(map,n,m);
cout<<s<<endl;
system("pause");
}