think: 1題目一開始自己使用鄰接表來做，結果就是樣本數據和自己思考的數據都可以通過，但是提交之后就是wrong answer，之后在博客上借鑒可前輩們的代碼，使用了鄰接矩陣來做，然后又wrong answer了，內心崩潰臨界狀態，然后對照前輩代碼，發現自己因為vis數組開的小了，按照題意至少應該200+，可自己只開了104，因此修改之后提交就AC了，感覺可能是因為進度有點被別的同學拉下了，所以內心焦急，還得多學會調節自己和提高效率，只有這樣才能從根本上解決問題，心態調節與提高效率是相輔相成的關系，自己既要學會更適合自己的學習方法，因為自己就是變化的，所以最合適的方法至少也是在一個輕微的細節不斷變化，學習心態，學習效率，學習方法，都得加油提高，只要自己不放棄，那便沒有真正意義上的失敗，失敗只是成功的前奏，只要堅持和反思，失敗不再持續可怕 2回歸題目，其實自己感覺這個題目雖然數據量并不大，但感覺還是使用鄰接表比較適合，因為數據的輸入方式很適合建立鄰接表，而鄰接表對于查詢操作來說時間復雜度要優于鄰接矩陣，廣度優先搜索，自己在這個題目的收獲就是其實可以直接把需要初始化數組的初始化直接放在BFS函數中，這樣更適合一次輸入，多次查詢的任務需求，還有自己之前基本都是把第一個的數據初始化放在BFS函數外面，自己這次是直接放在BFS函數中，這樣感覺整體上簡潔明了許多，再就是全局變量的使用，之前做圖的題目的時候一直沒有考慮的全局變量方面的反思，這次注意到就簡單反思一下，在很多優先變量的輸入中其實可能會在多個函數中使用，如果一直使用實參傳遞給形參感覺可能會比較略顯繁瑣，使用多個函數的時候就可以考慮將優先變量使用為全局變量，但是卻一定要注意不能在函數中出現重名，之前自己就犯過這樣的錯誤，所以全局變量不能隨便就用，要有計劃的使用，而且在CodeBlocks里面，至少自己調試bug的時候似乎watch窗口并不顯示全局定義的變量，那時候就得自己推演全局變量的變化 3基于結構體數組的隊列思想
sdut原題鏈接
廣度優先搜索練習之神奇的電梯 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 有一座已知層數為n的高樓，這座高樓的特殊之處在于只能靠電梯去上下樓，所以要去到某一層要非常耽誤時間，然而更悲哀的是，這座高樓的電梯是限號的，小鑫最開始的時候在1層，他想去第x層，問題是他最起碼要經過多少層(包含第x層)才能到達第x層。
Input 多組輸入。 第一行是三個正整數n,m,q。分別代表樓的總層數，給定的m條信息和q次查詢。 接下來的m行，每行的第一個整數pos代表這是第pos層的電梯，第二個數代表從這一層可以去的樓層總共有num個，之后的num個數字代表從第pos層代表可以去的樓層。 最后的q行，每行一個整數代表小鑫想去的樓層號碼。 1<=m,pos,num<=n<=200 1<=q<=20
Output 對于每次詢問輸出一個整數，占一行。代表如果要去某個樓層最少要經過多少層，如果到不了的話就輸出-1。
Example Input 10 4 3 1 2 6 7 3 4 4 6 8 10 5 2 2 3 7 3 10 5 6 4 5 9
Example Output 5 3 -1
Hint BFS+鄰接矩陣（個人建議）
Author Casithy
以下為accepted代碼——BFS+鄰接矩陣
#include <stdio.h>#include <string.h>struct node{ int x; int size;}link[204], t, f;int tp, op, n;int map[204][204], vis[204];void BFS(int x1, int X){ memset(vis, 0, sizeof(vis)); memset(link, 0, sizeof(link)); tp = op = 0; t.x = 1; t.size = 0; link[tp++] = t; vis[t.x] = 1; while(op < tp) { f = link[op++]; if(f.x == X) { printf("%d/n", f.size + 1); return; } for(int i = 1; i <= n; i++) { if(map[f.x][i] == 1 && vis[i] == 0) { t.x = i; t.size = f.size + 1; link[tp++] = t; vis[i] = 1; } } } printf("-1/n");}int main(){ int m, q, u, num, v, X; while(scanf("%d %d %d", &n, &m, &q) != EOF) { memset(map, 0, sizeof(map)); while(m--) { scanf("%d", &u); scanf("%d", &num); while(num--) { scanf("%d", &v); map[u][v] = 1; } } while(q--) { scanf("%d", &X); BFS(1, X); } } return 0;}/***************************************************User name: Result: AcceptedTake time: 16msTake Memory: 276KBSubmit time: 2017-02-17 09:49:38****************************************************/以下為wrong answer代碼——BFS+鄰接表 .???
#include <stdio.h>#include <string.h>#include <stdlib.h>struct node{ int Data; struct node *next;}*map[204], *p;struct node1{ int x; int size;}link[204], ans, t, f;int vis[204];int tp, op;void BFS(int x1, int X){ ans.x = x1; ans.size = 1; link[tp++] = ans; while(op < tp) { t = link[op++]; if(t.x == X) { printf("%d/n", t.size); return; } p = map[t.x]; while(p != NULL) { if(vis[p->Data] == 0) { f.x = p->Data; f.size = t.size + 1; link[tp++] = f; vis[p->Data] = 1; } p = p->next; } } printf("-1/n");}int main(){ int n, m, i, q, u, num, v, X; while(scanf("%d %d %d", &n, &m, &q) != EOF) { for(i = 0; i < n; i++) map[i] = NULL; while(m--) { scanf("%d", &u); if(map[u] == NULL) { p = (struct node *)malloc(sizeof(struct node)); p->Data = u; p->next = NULL; map[u] = p; } scanf("%d", &num); while(num--) { scanf("%d", &v); p = (struct node *)malloc(sizeof(struct node)); p->Data = v; p->next = NULL; p->next = map[u]->next; map[u]->next = p; } } while(q--) { scanf("%d", &X); tp = op = 0; memset(vis, 0, sizeof(vis)); memset(link, 0, sizeof(link)); BFS(1, X); } } return 0;}/***************************************************User name: Result: Wrong AnswerTake time: 32msTake Memory: 3000KBSubmit time: 2017-02-17 09:12:20****************************************************/新聞熱點
疑難解答
