现在有一个城市销售经理,需要从公司出发,去拜访市内的商家,已知他的位置以及商家的位置,但是由于城市道路交通的原因,他只能在左右中选择一个方向,在上下中选择一个方向,现在问他有多少种方案到达商家地址。给定一个地图map及它的长宽n和m,其中1代表经理位置,2代表商家位置,-1代表不能经过的地区,0代表可以经过的地区,请返回方案数,保证一定存在合法路径。保证矩阵的长宽都小于等于10。

include "stdafx.h"

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std; class Visit {
public:
int countPath(vector<vector<int> > map, int n, int m) {
int count=0;
int compX, compY, sellerX,sellerY;
for (int i = 0;i < map.size();i++)
{
for (int j = 0;j < map[0].size();j++)
{
if (map[i][j] == 1)
{
compX = i; compY = j;
// cout << "i:" << i << endl;
// cout << "j:" << j << endl;
}
if (map[i][j] == 2)
{
sellerX = i, sellerY = j;
// cout << "i:" << i << endl;
// cout << "j:" << j << endl;
}
}
}
int minX = min(sellerX,compX);
int maxX = max(sellerX, compX);
int minY = min(sellerY, compY);
int maxY = max(sellerY, compY); vector<vector<int> > mapp;
for (int i = minX;i <= maxX;i++)
{
vector<int> vec;
for (int j = minY;j <= maxY;j++)
{
vec.push_back(map[i][j]);
}
mapp.push_back(vec);
}
if (mapp[0][0] == 1)
{
return getPathLR(mapp);
}else if(mapp[mapp.size()-1][0] == 1)
{
return getPathHR(mapp);
}
else if (mapp[0][mapp[0].size()-1] == 1)
{
return getPathLL(mapp);
}
else
{
return getPathHL(mapp);
} } int getPathLR(vector<vector<int> > map) { // if (map[0][0] != 1) return 0; if (map.size() == 1)
{
int num = 0;
for (int i = 0;i < map[0].size();i++)
{
if (map[0][i] == -1)
{
num = 0;
break;
}
if (map[0][i] == 2)
{
num = 1;
break;
}
}
return num;
}
if (map[0].size() == 1)
{
int num = 0;
for (int i = 0;i < map.size();i++)
{
if (map[i][0] == -1)
{
num = 0;
break;
}
if (map[i][0] == 2)
{
num = 1;
break;
}
}
return num;
} return getPathLR(deleteRowLR( map) )+ getPathLR(deleteColLR(map)); } vector<vector<int> > deleteRowLR(vector<vector<int> > map)
{
map.erase(map.begin());
return map;
}
vector<vector<int> > deleteColLR(vector<vector<int> > map)
{
for (int i = 0;i < map.size();i++)
{
map[i].erase(map[i].begin());
}
return map;
} int getPathHR(vector<vector<int> > map) { // if (map[map.size()-1][0] != 1) return 0; if (map.size() == 1)
{
int num = 0;
for (int i = 0;i < map[0].size();i++)
{
if (map[0][i] == -1)
{
num = 0;
break;
}
if (map[0][i] == 2)
{
num = 1;
break;
}
}
return num;
}
if (map[0].size() == 1)
{
int num = 0;
for (int i = map.size()-1;i >=0;i--)
{
if (map[i][0] == -1)
{
num = 0;
break;
}
if (map[i][0] == 2)
{
num = 1;
break;
}
}
return num;
} return getPathHR(deleteRowHR(map)) + getPathHR(deleteColHR(map)); } vector<vector<int> > deleteRowHR(vector<vector<int> > map)
{
map.erase(map.end()-1);
return map;
}
vector<vector<int> > deleteColHR(vector<vector<int> > map)
{
for (int i = 0;i < map.size();i++)
{
map[i].erase(map[i].begin());
}
return map;
} int getPathLL(vector<vector<int> > map) {
// if (map[0][map[0].size() - 1] != 1) return 0;
int count = 0;
if (map.size() == 1)
{
int num = 0;
for (int i = map[0].size()-1;i >=0;i--)
{
if (map[0][i] == -1)
{
num = 0;
break;
}
if (map[0][i] == 2)
{
num = 1;
break;
}
}
return num;
} if (map[0].size() == 1)
{
int num = 0;
for (int i = 0;i < map.size();i++)
{
if (map[i][0] == -1)
{
num = 0;
break;
}
if (map[i][0] == 2)
{
num = 1;
break;
}
}
return num;
} return getPathLL(deleteRowLL(map)) + getPathLL(deleteColLL(map)); } vector<vector<int> > deleteRowLL(vector<vector<int> > map)
{
map.erase(map.begin());
return map;
}
vector<vector<int> > deleteColLL(vector<vector<int> > map)
{
for (int i = 0;i < map.size();i++)
{
map[i].erase((map[i].end()-1));
}
return map;
} int getPathHL(vector<vector<int> > map) { // if (map[map.size()-1][map[0].size() - 1] != 1) return 0; if (map.size() == 1)
{
int num = 0;
for (int i = map[0].size()-1;i >=0;i--)
{
if (map[0][i] == -1)
{
num = 0;
break;
}
if (map[0][i] == 2)
{
num = 1;
break;
}
}
return num;
}
if (map[0].size() == 1)
{
int num = 0;
for (int i = map.size()-1;i >=0;i--)
{
if (map[i][0] == -1)
{
num = 0;
break;
}
if (map[i][0] == 2)
{
cout << "执行了" << endl;
num = 1;
break;
}
}
return num;
} return getPathHL(deleteRowHL(map)) + getPathHL(deleteColHL(map)); } vector<vector<int> > deleteRowHL(vector<vector<int> > map)
{
map.erase(map.end()-1);
return map;
}
vector<vector<int> > deleteColHL(vector<vector<int> > map)
{
for (int i = 0;i < map.size();i++)
{
map[i].erase((map[i].end() - 1));
}
return map;
} };
int main()
{
vector<vector<int> > map;
vector<int> vec1 = { 0,1,0 };
vector<int> vec2 = { 2,0,0 };
map.push_back(vec1);
map.push_back(vec2);
Visit v;
cout << v.countPath(map, 2, 3) << endl;; return 0;
}
上一篇:WebRTC源码分析:音频模块结构分析


下一篇:Oracle 数据库 基础学习 (一) SQL基本知识