【走迷宫】

题目

DFS代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int matrix[N][N];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dis[N][N];
void dfs(int x, int y, int cnt)
{if(cnt > dis[n-1][m-1]) return;if(x == n-1 && y == m-1) return;for(int i = 0; i < 4; i++){int nx = x + dx[i], ny = y + dy[i];if(nx < 0 || ny < 0 || nx >= n || ny >= m || matrix[nx][ny]) continue;if(dis[nx][ny] > dis[x][y] + 1){dis[nx][ny] = dis[x][y] + 1;dfs(nx, ny, cnt+1);}}
}
int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){scanf("%d", &matrix[i][j]);}}memset(dis, 0x3f, sizeof dis);        dis[0][0] = 0;dfs(0, 0, 0);cout << dis[n-1][m-1];return 0;
}

优化：

1.if(cnt >= res) return; （较好）

2.if(dis[x][y] < cnt) return; （较好）
   else dis[x][y] = cnt;

3.         if(dis[nx][ny] > dis[x][y] + 1) (非常好)
        {
            dis[nx][ny] = dis[x][y] + 1;
            dfs(nx, ny, cnt+1);
        }

优化1+优化2都不如单用优化3

优化3可以替代优化2，同时可以不需要visited访问数组、cnt参数、res。

优化1可以和优化3搭配(需要cnt参数)，效果最好，比单用优化3快一倍。为什么？

注意：优化2中和优化3中均不能加等号，前者会导致错误，后者会TLE。为什么？

BFS代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define f first
#define s secondconst int N = 110;
int g[N][N];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dis[N][N];
int bfs(int a, int b)
{queue<PII> q;q.push({a,b});dis[a][b] = 0;while(q.size()){PII u = q.front();q.pop();for(int i = 0; i < 4; i++){int nx = u.f + dx[i], ny = u.s + dy[i];if(nx >= 0 && ny >= 0 && nx < n && ny < m && !g[nx][ny] && dis[nx][ny] == -1){q.push({nx, ny});dis[nx][ny] = dis[u.f][u.s] + 1;}}}return dis[n-1][m-1];
}
int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){scanf("%d", &g[i][j]);}}memset(dis, -1, sizeof dis);cout << bfs(0, 0);return 0;
}

数组实现

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define f first
#define s secondconst int N = 110;
int g[N][N];
PII q[N * N];
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dis[N][N];
int bfs(int a, int b)
{int h = 0, t = 0;q[0] = {a, b};dis[a][b] = 0;while(h <= t){auto u = q[h++];for(int i = 0; i < 4; i++){int nx = u.f + dx[i], ny = u.s + dy[i];if(nx >= 0 && ny >= 0 && nx < n && ny < m && !g[nx][ny] && dis[nx][ny] == -1){q[++t] = {nx, ny};dis[nx][ny] = dis[u.f][u.s] + 1;}}}return dis[n-1][m-1];
}
int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){scanf("%d", &g[i][j]);}}memset(dis, -1, sizeof dis);cout << bfs(0, 0);return 0;
}