2022 年 11 月 13 日

C++, 資訊學科能力競賽

Q8-無環圖上色

2022.11.13 AM 09:30 by CBJ

來源 : 111資訊學科能力競賽複賽-彰雲嘉
標籤 : BFS(廣度優先搜尋)、結構(struct)、自定義排序
難易度 : 6

題目敘述 ： 
給定彩虹色共七種(R:紅,O:橙,Y:黃,G:綠,B:藍,I:靛,V:紫)，請對於一張無環圖進行塗色(注意：塗在線上)，若塗色時遇到相同顏色，則不要再塗一次，反之若遇到不同顏色，則需要蓋過去，所求為每個顏色塗的次數(由彩虹順序輸出，若為0則不用輸出)

輸入說明 ：
首先有一個正整數n,表示結點個數。
再來會有n-1行，每行有兩個整數x,y，用空白隔開，表示x,y相鄰。
再來會有一個正整數m,表示指令個數。
對於接下來的m行指令，會有a,b,c三個值，其中a,b為整數，c為大寫字元(必屬於彩虹色)，指的是要將a~b之間的所有線段塗上顏色c。

範例測資 ： 
範例輸入
8
0 1
1 2
1 3
3 4
4 5
4 6
4 7
4
0 7 B
2 0 B
3 7 R
5 7 V
範例輸出
R 2
B 5
V 2

測資說明 ：

範例測資的圖形應如下：

             (3)       (5)
            /   \      /
           B   B->R   V     
          /       \  /       
(0)- B -(1)       (4)- - -(6)
        /           \    
       B           B->R->V  
      /               \
    (2)               (7)

解題想法 : 
依照題意建好圖以後，先bfs找到終點，過程對於每個點記錄前一個點，再回溯塗色，過程中記錄塗色次數，最後依照彩虹順序排序輸出即可。

//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/%E8%B3%87%E8%A8%8A%E5%AD%B8%E7%A7%91%E8%83%BD%E5%8A%9B%E7%AB%B6%E8%B3%BD/111%E5%BD%B0%E9%9B%B2%E5%98%89/Q8-%E7%84%A1%E7%92%B0%E5%9C%96%E4%B8%8A%E8%89%B2.cpp

#include<iostream>
#include<map>
#include<utility>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<algorithm>
using namespace std;
int n,m;
map<char,int> order;
bool cmp(pair<char,int> &a, pair<char,int> &b){
    return order[a.first] < order[b.first];
}
struct node{
    int num;
    vector<int> linked;
    char color_with_prev;
};
map<int,node*> nodes;
map<char,int>times;
void trace(int now, int target, map<int,node*> &prev, char color){
    if(now==target) return;
    if(color != nodes[now]->color_with_prev){
        nodes[now]->color_with_prev=color;
        times[color]++;
    }
    trace(prev[nodes[now]->num]->num,target,prev,color);
}

void bfs(int from,int to,char color){
    queue<node*>q;
    set<node*>visited;
    map<int,node*> prev;
    q.push(nodes[from]);
    while(!q.empty()){
        node* cur=q.front();
        if(nodes[cur->num] == nodes[to]){
            trace(to,from,prev,color);
        }
        visited.insert(nodes[cur->num]);
        for(int a:nodes[cur->num]->linked){
            if(visited.find(nodes[a]) != visited.end()){
                continue;
            }
            q.push(nodes[a]);
            prev[a]=cur;
        }
        q.pop();
    }
}
int main(){
    times['R']=times['O']=times['Y']=times['G']=times['B']=times['I']=times['V']=0;
    order['R']=0; order['O']=1; order['Y']=2;
    order['G']=3; order['B']=4; order['I']=5; order['V']=6;
    unordered_set<int>st;
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        if(st.find(x)==st.end()){
            nodes[x]=new node;
            nodes[x]->num=x;
        }
        nodes[x]->linked.push_back(y);
        if(st.find(y)==st.end()){
            nodes[y]=new node;
            nodes[y]->num=y;
        }
        nodes[y]->linked.push_back(x);
        st.insert(x);
        st.insert(y);
    }
    cin>>m;
    while(m--){
        int x,y;
        char c;
        cin>>x>>y>>c;
        bfs(x,y,c);
    }
    vector<pair<char,int>> ans;
    for(char c:"ROYGBIV"){
        if(times[c] != 0) ans.push_back({c,times[c]});
    }
    sort(ans.begin(),ans.end(),cmp);
    for(pair<char,int> p: ans){
        cout<<p.first<<" "<<p.second<<"\n";
    }
    return 0;
}

相關文章

發佈留言取消回覆