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;
}
發佈留言