think: 1結構數組+廣度優先搜索 2逆推思想
sdut原題鏈接
圖結構練習——BFS——從起始點到目標點的最短步數 Time Limit: 1000MS Memory Limit: 65536KB PRoblem Description
在古老的魔獸傳說中，有兩個軍團，一個叫天災，一個叫近衛。在他們所在的地域，有n個隘口，編號為1..n，某些隘口之間是有通道連接的。其中近衛軍團在1號隘口，天災軍團在n號隘口。某一天，天災軍團的領袖巫妖王決定派兵攻打近衛軍團，天災軍團的部隊如此龐大，甚至可以填江過河。但是巫妖王不想付出不必要的代價，他想知道在不修建任何通道的前提下，部隊是否可以通過隘口及其相關通道到達近衛軍團展開攻擊；如果可以的話，最少需要經過多少通道。由于n的值比較大（n<=1000），于是巫妖王找到了擅長編程的你 =_=，請你幫他解決這個問題，否則就把你吃掉變成他的魔法。為了拯救自己，趕緊想辦法吧。
Input
輸入包含多組，每組格式如下。
第一行包含兩個整數n,m（分別代表n個隘口，這些隘口之間有m個通道）。
下面m行每行包含兩個整數a，b；表示從a出發有一條通道到達b隘口（注意：通道是單向的）。
Output
如果天災軍團可以不修建任何通道就到達1號隘口，那么輸出最少經過多少通道，否則輸出NO。
Example Input
2 1 1 2 2 1 2 1
Example Output
NO 1
Hint Author 趙利強
以下為accepted代碼
#include <stdio.h>#include <string.h>int map1[1002][1002], visit[2000];struct node{ int x; int ans;}q[2000];void BFS(int i, int n){ int s = 1, e = 1, j; struct node f1, f2; f1.x = i; f1.ans = 0; q[s++] = f1; visit[f1.x] = 1; while(s > e) { f1 = q[e++]; if(f1.x == 1) { printf("%d/n", f1.ans); return; } for(j = 1; j <= n; j++) { f2.x = j; if(visit[f2.x] == 0 && map1[f1.x][f2.x] == 1) { visit[f2.x] = 1; f2.ans = f1.ans + 1; q[s++] = f2; } } } printf("NO/n"); return;}int main(){ int n, m, i, a, b; while(scanf("%d %d", &n, &m) != EOF) { memset(map1, 0, sizeof(map1)); memset(visit, 0, sizeof(visit)); for(i = 0; i < m; i++) { scanf("%d %d", &a, &b); map1[a][b] = 1; } BFS(n, n); } return 0;}/***************************************************User name: Result: AcceptedTake time: 60msTake Memory: 2012KBSubmit time: 2017-02-15 21:45:57****************************************************/新聞熱點
疑難解答
