C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-08-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param CityMap int整型vector<vector<>>
* @param n int整型
* @param m int整型
* @return int整型
*/
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int countPath(vector<vector<int> >& CityMap, int n, int m) {
vector<int> d(n * m, 0x3f3f3f3f), f(n * m, 0);
int src, dst;
for(int i = 0; i < n ; i++){
for(int j = 0; j < m; j++){
if(CityMap[i][j] == 1){
src = i * m + j;
}else if(CityMap[i][j] == 2){
dst = i * m + j;
}
}
}
queue<int> q;
q.push(src);
d[src] = 0, f[src] = 1;
while(!q.empty()){
int t = q.front(); q.pop();
int x = t / m, y = t % m, nx, ny, nt;
for(int i = 0; i < 4; i++){
nx = x + dx[i], ny = y + dy[i];
nt = nx * m + ny;
if(nx >= 0 && nx < n && ny >= 0 && ny < m && CityMap[nx][ny] != -1){
if(d[nt] > d[t] + 1){
d[nt] = d[t] + 1;
q.push(nt);
}
if(d[nt] == d[t] + 1) f[nt] += f[t];
}
}
}
return f[dst];
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-01-29
class Solution {
public:
/*
方法一：深度优先搜索
复杂度分析
时间复杂度：需要遍历地图上所有的位置，所以时间复杂度是O(n∗m)
空间复杂度：O(n*m)
*/
int countPath1(vector<vector<int> >& CityMap, int n, int m) {
row = n;
col = m;
visited.resize(n);
for(int i = 0; i < n; ++i) {
visited[i].resize(m);
}
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
if(CityMap[i][j] == 2) {
startx = i;
starty = j;
}
}
}
dfs(CityMap, startx, starty);
return count;
}
/*
方法二：广度优先搜索+动态规划
*/
int countPath(vector<vector<int> >& CityMap, int n, int m) {
//path_nums为dp数组，用于记录起点到当前位置最短距离的方案数
int visited[n][m], path_nums[n][m];
int directions[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
memset(visited, 0, sizeof(visited));
queue<pair<int, int>> Que;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(CityMap[i][j] == 1) {
Que.push({i, j});
path_nums[i][j] = 1;
visited[i][j] = 1;
}
while(!Que.empty()) {
int size = Que.size();
while(size--) {
auto t = Que.front();
Que.pop();
for(int i = 0; i < 4; ++i) {
int new_x = t.first + directions[i][0], new_y = t.second + directions[i][1];
if(new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || CityMap[new_x][new_y] == -1)
continue;
if(!visited[new_x][new_y]) {
visited[new_x][new_y] = visited[t.first][t.second] + 1;
path_nums[new_x][new_y] = path_nums[t.first][t.second];
Que.push({new_x, new_y});
} else {
if(visited[new_x][new_y] == visited[t.first][t.second] + 1)
path_nums[new_x][new_y] += path_nums[t.first][t.second];
}
}
}
}
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(CityMap[i][j] == 2)
return path_nums[i][j];
return 0;
}
private:
int dires[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
vector<vector<int>> visited;
int pathlen = 0, shortestlen = 101;
int count = 0;
int row, col;
int startx, starty;
void dfs(vector<vector<int> >& CityMap, int x, int y) {
int n = row, m = col;
//路径长度大于最优即返回，减少计算次数
//如果遇到越界、遇到障碍物、已经访问过、或者距离更大的情况，直接返回
if(x<0 || x>=n || y<0 || y>=m || CityMap[x][y]==-1 || visited[x][y]==1 || pathlen>=shortestlen){
return;
}
++pathlen;
visited[x][y] = 1;
if(CityMap[x][y] == 1){
if(pathlen < shortestlen){
shortestlen = pathlen;
count = 1;
}
else if(pathlen == shortestlen){ //找到一条合法路径
++count;
}
visited[x][y] = 0;
--pathlen;
return;
}
//往四个方向进行深度优先搜索
for(int i = 0; i < 4; ++i){
int xx = x + dires[i][0];
int yy = y + dires[i][1];
dfs(CityMap, xx, yy);
}
visited[x][y] = 0; //每次搜索完，重置标记数组
--pathlen;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 432KB, 提交时间: 2022-07-24
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param CityMap int整型vector<vector<>>
* @param n int整型
* @param m int整型
* @return int整型
*/
vector<int> dx = {1,-1,0,0};
vector<int> dy = {0,0,1,-1};
int countPath(vector<vector<int> >& CityMap, int n, int m) {
// write code here
int res = 0;
vector<vector<int> > vis(n,vector<int>(m,0));
queue<int> q;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(CityMap[i][j]==1) {
q.emplace(i*m+j);
q.emplace(-1);
vis[i][j]=1;
break;
}
}
if(!q.empty()) break;
}
bool flag = false;
while(!q.empty()){
if(q.front()==-1 && flag){
break;
}
if(q.front()==-1){
q.pop();
q.emplace(-1);
continue;
}
int x = q.front()/m, y = q.front()%m;
vis[x][y] = 1;
q.pop();
if(CityMap[x][y] == 2){
flag=true;
res++;
continue;
}
if(flag) continue;
for(int i=0;i<4;i++){
int xx = x+dx[i], yy = y+dy[i];
if(xx<0 || xx>=n || yy<0 || yy>=m || CityMap[xx][yy] == -1 || vis[xx][yy] == 1) continue;
q.emplace(xx*m+yy);
}
}
return res;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 468KB, 提交时间: 2022-05-22
class MPoint{
public:
int m_x;
int m_y;
MPoint(int x, int y):m_x(x),m_y(y){
}
};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param CityMap int整型vector<vector<>>
* @param n int整型
* @param m int整型
* @return int整型
*/
bool isvaild(vector<vector<int> >& CityMap, int x, int y){
int n = CityMap.size();
int m = CityMap[0].size();
if(x<0 || x>=m || y<0 || y>=n || CityMap[y][x] == -1) return false;
return true;
}
MPoint next_points(MPoint point,int i){
const int direction[4][2] = {0,1,0,-1,1,0,-1,0};
return MPoint(point.m_x + direction[i][0], point.m_y + direction[i][1]);
}
int countPath(vector<vector<int> >& CityMap, int n, int m) {
// write code here
queue<MPoint> q;
int start_x, start_y;
int end_x, end_y;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(CityMap[i][j] == 2){
end_x = j;
end_y = i;
continue;
}
if(CityMap[i][j] == 1){
start_x = j;
start_y = i;
continue;
}
}
}
vector<vector<int>> visited(n,vector<int>(m, 0));
vector<vector<int>> distance(n,vector<int>(m,0));
vector<vector<int>> path_counts(n,vector<int>(m, 0));
q.push(MPoint(start_x, start_y));
visited[start_y][start_x] = 1;
path_counts[start_y][start_x] = 1;
int step = 0;
int count = 0;
while(!q.empty()){
int sz = q.size();
while(sz--){
auto point = q.front();
q.pop();
if(CityMap[point.m_y][point.m_x] == 2) return path_counts[point.m_y][point.m_x];
for(int i=0;i<4;i++){
auto next_point = next_points(point, i);
if(isvaild(CityMap, next_point.m_x, next_point.m_y)){
path_counts[next_point.m_y][next_point.m_x] += path_counts[point.m_y][point.m_x];
if(visited[next_point.m_y][next_point.m_x] ==0) q.push(next_point);
visited[next_point.m_y][next_point.m_x] = 1;
}
}
}
}
cout << "fdsa";
return path_counts[end_y][end_x];;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 488KB, 提交时间: 2022-03-16
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param CityMap int整型vector<vector<>>
* @param n int整型
* @param m int整型
* @return int整型
*/
int minCost = 999; //记录最短路径的距离
int cnt = 0; //记录最短路径的方案
int cost = 0; //记录路径距离
int dx[4] = {0, 1, 0, -1}; //右 下 左 上
int dy[4] = {1, 0, -1, 0};
int ex, ey, sx, sy;
vector<vector<bool>> vis;
void dfs(vector<vector<int>>& CityMap, int sx, int sy){
int n = CityMap.size(), m = CityMap[0].size();
//220315_DXM_这比放在for循环中调用时间短
if(sx < 0 || sx >= n || sy < 0 || sy >= m ||
CityMap[sx][sy] == -1 || vis[sx][sy] == true || cost >= minCost) return;
//220315_DXM_可访问，设置为已访问状态
cost++;
vis[sx][sy] = true;
if(CityMap[sx][sy] == 2){
if(cost < minCost){
minCost = cost;
cnt = 1; //重置最短路径
}
else if(cost == minCost) cnt++;
//220315_DXM_回溯
vis[sx][sy] = false;
cost--;
return;
}
for(int i = 0; i < 4; i++){
int nx = sx + dx[i], ny = sy + dy[i];
dfs(CityMap, nx, ny);
}
vis[sx][sy] = false;
cost--;
}
int countPath(vector<vector<int> >& CityMap, int n, int m) {
int ans = 0;
vis.resize(n);
for(int i = 0; i < n; i++) vis[i].resize(m);
//220315_DXM_找到地图中的起点和终点
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(CityMap[i][j] == 1) sx = i, sy = j;
}
}
dfs(CityMap, sx, sy);
return cnt;
}
};
