C++题解

#include <deque>
#include <iostream>
#include <vector>
using namespace std;

const int INF = 0x3F3F3F3F;

struct Node{
	int x, y;
	
	Node() = default;
	Node(int x, int y) : x(x), y(y) {}
};

int bfs(Node &s, vector<string> &g, 
	vector<vector<int>> &dist, vector<vector<bool>> &st, 
	int n, int m);

int main() {
	int n, m;
	cin >> n >> m;
	vector<string> g(n);
	
	for (int i = 0; i < n; ++i) {
		cin >> g[i];
	}
	
	vector<vector<int>> dist(n + 1, vector<int>(m + 1, INF));
	vector<vector<bool>> st(n + 1, vector<bool>(m + 1, false));
	
	Node t = {0, 0};
	int res = bfs(t, g, dist, st, n, m);
	
	if (res == INF) {
		cout << "NO SOLUTION" << endl;
	} else {
		cout << dist[n][m] << endl;
	}
	
	return 0;
}

int bfs(Node &s, vector<string> &g, 
    	vector<vector<int>> &dist, vector<vector<bool>> &st, 
    	int n, int m) {
    deque<Node> dq;
    dist[s.x][s.y] = 0;
    dq.emplace_back(s);
    
    string x{"\\/\\/"};
    const int dx[] = {-1, -1, 1, 1};
    const int dy[] = {-1, 1, 1, -1};
    
    const int dlx[] = {-1, -1, 0, 0};
    const int dly[] = {-1, 0, 0, -1};
    
    while (!dq.empty()) {
        auto t = dq.front();
        dq.pop_front();
        
        if (!st[t.x][t.y]) {
            st[t.x][t.y] = true;
            for (int i = 0; i < 4; ++i) {
                int tx = t.x + dx[i];
                int ty = t.y + dy[i];
                if (0 <= tx && tx <= n && 0 <= ty && ty <= m) {
                    const int lx = t.x + dlx[i];
                    const int ly = t.y + dly[i];
                    const int w = g[lx][ly] != x[i] ? 1 : 0;
                    const int d = dist[t.x][t.y] + w;
                    if (d < dist[tx][ty]) {
                        dist[tx][ty] = d;
                        if (w == 0) {
                            dq.emplace_front(tx, ty);
                        } else {
                            dq.emplace_back(tx, ty);
                        }
                    }
                }
            }
        }
    }
    return dist[n][m];
}

内存5.29MB
时间8ms