【leetcode】颜色交替的最短路径(bfs,dfs)

在一个有向图中，节点分别标记为 0, 1, …, n-1。这个图中的每条边不是红色就是蓝色，且存在自环或平行边。

red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的最短路径的长度，且路径上红色边和蓝色边交替出现。如果不存在这样的路径，那么 answer[x] = -1。

示例 1：

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]
示例 2：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]
示例 3：

输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
输出：[0,-1,-1]
示例 4：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
输出：[0,1,2]
示例 5：

输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
输出：[0,1,1]

提示：

1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

链接：https://leetcode-cn.com/problems/shortest-path-with-alternating-colors

思路分析：

这是一道有向无权图的最短路问题，不过这道题比模板多加了几个新的条件：

1. 存在自环和平行边。
2. 区分颜色，并且要按照颜色交替进行。

如果按照模板的bfs，我们就会通过标记节点保证不会重复遍历。但是如果按照这样的做法，**自环的情况就很难处理了。**因为一个节点可能需要遍历多次。比如一个节点到下一个节点只有蓝边，节点自环有红边，而节点又需要走红边。这时候节点可以先走自环的红边再走到下一个节点。
那么，怎么处理这种情况呢？
我们把对节点的vis改成对边的vis即可。
定义bool vis[i][j][k] 表示 i 到 j 的颜色为 k 的边是否被访问过。

于是，bfs就好写了。
定义节点的成员有：编号id，颜色c，当前路径长度st.
每次出队，更新ans，然后遍历该节点的所有出度节点，如果边的颜色和节点的颜色不一样并且该边未
访问过，就将该出度节点压进队列即可。

class Solution {
public:
    struct node{
        int id, c, st;  //1红 2蓝 3红蓝
    };
    
    int mp[102][102];
    bool vis[102][102][3];	//表示 i->j颜色为k的边 
    
    void bfs(vector<int> &ans, int n, int s, int c)
    {
        node t, tt;
        t.id = s, t.c = c, t.st = 0;
        queue<node> Q;
        Q.push(t);
        while(!Q.empty())
        {
            t = Q.front();
            Q.pop();
            ans[t.id] = min(ans[t.id], t.st);	//能到达一个节点，就是一个最短路 
            int clr = t.c==1?2:1;	//clr表示与当前节点相反的颜色
            for(int i = 0;i < n;i++)
            {
                if(mp[t.id][i] > 0 && mp[t.id][i] != t.c && !vis[t.id][i][clr])	//颜色与当前节点不同，出度边未被遍历过   
                {
                    tt.id = i, tt.st = t.st+1, tt.c = clr;
                    vis[t.id][i][tt.c] = 1;
                    Q.push(tt);
                }
            }
        }
    }

    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        memset(mp,0,sizeof(mp));
        vector<int> ans(n,0x3f3f3f3f);
        for(int i = 0;i < red_edges.size();i++)
        {
            int x = red_edges[i][0], y = red_edges[i][1];
            mp[x][y] = 1;
        }
        for(int i = 0;i < blue_edges.size();i++)
        {
            int x = blue_edges[i][0], y = blue_edges[i][1];
            if(mp[x][y] == 1)	//存在红蓝平行边，意味着该节点红蓝均通，定义为 3 
            mp[x][y] = 3;
            else mp[x][y] = 2;
        }
        memset(vis,0,sizeof(vis));
        bfs(ans,n,0,1);
        memset(vis,0,sizeof(vis));
        bfs(ans,n,0,2);
        for(int i = 0;i < ans.size();i++)
        if(ans[i] == 0x3f3f3f3f) ans[i] = -1;
        return ans;
    }
};

/*
3
[[0,1],[1,2]]
[]
3
[[0,1]]
[[2,1]]
3
[[1,0]]
[[2,1]]
3
[[0,1]]
[[1,2]]
3
[[0,1],[0,2]]
[[1,0]]
*/

下面附赠一个超时的dfs写法。

class Solution {
public:
    struct node{
        int to, c;
    };

    vector<node> edge[102];	//建立边邻接表
    bool vis[102][102][3];

    void dfs(vector<int> &ans, int n, int id, int c, int st)
    {
        node t;
        ans[id] = min(ans[id], st);
        int clr = c==1?2:1;
        for(int i = 0;i < edge[id].size();i++)
        {
            t = edge[id][i];
            int to = t.to, clr = t.c;
            if(clr != c && !vis[id][to][clr])
            {
                vis[id][to][clr] = 1;
                dfs(ans,n,to,clr,st+1);
                vis[id][to][clr] = 0;
            }
        }
    }


    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
        vector<int> ans(n,0x3f3f3f3f);
        node t;
        for(int i = 0;i < red_edges.size();i++)
        {
            int x = red_edges[i][0], y = red_edges[i][1];
            t.to = y, t.c = 1;
            edge[x].push_back(t);
        }
        for(int i = 0;i < blue_edges.size();i++)
        {
            int x = blue_edges[i][0], y = blue_edges[i][1];
            t.to = y, t.c = 2;
            edge[x].push_back(t);
        }
        memset(vis,0,sizeof(vis));
        dfs(ans,n,0,1,0);
        memset(vis,0,sizeof(vis));
        dfs(ans,n,0,2,0);
        for(int i = 0;i < n;i++) if(ans[i] == 0x3f3f3f3f) ans[i] = -1;
        return ans;
    }
};