→ Lipstick12:謝謝 希望這樣有比較好看一點! 09/18 20:29
( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
( 未必需要依照此格式，文章條理清楚即可 )
題號： 336 A node too far
遇到的問題： WA
有問題的code： (請善用置底文的標色功能)
Code 有點長 可能要讓各位傷眼睛了 抱歉
/* ACM-336 A Node Too Far - Array Version*/
#include<stdio.h>
#include<stdlib.h>
FILE *input;
void check(int number);
void ini_visit();
int query(int number);
void BFS(int start_v,int TTL );
void connect(int p, int q );
void initialize();
int trans[30] ={0}; /* 記下 1~30個節點對應的value */
int graph[30][30] ; /* 圖形 */
int right = 0; /* 記下有幾個節點 */
int steps[30] = {0}; /* 從start_vertex 到i個節點的steps*/
int visit[30] ={0}; /* visit or not */
int queue[30] ={0}; /* queue to implement bfs*/
int head = 0; /* head of queue*/
int tail = 0; /* tail of queue*/
int unreach = 0;/* 有幾個節點不能到達 */
int main(void){
int a,b;
int p,q;
int number = 1 ;
int counter;
int cas = 1;
int m,n; /* query number */
input = fopen("abc.txt","r");
//input = stdin;
fscanf(input,"%d",&number);
initialize();
while ( number != 0 ){
for ( counter = 0 ; counter < number ; counter ++ ){
fscanf(input,"%d%d",&a,&b);
check(a);
check(b);
if ( a == b ) continue;
p = query(a);
q = query(b);
connect(p,q); /* construct the graph */
}
fscanf(input,"%d%d",&m,&n);
while ( m != 0 && n != 0 ){
ini_visit();
BFS(query(m),n);
steps[query(m)] = 0;
for ( a = 0 ; a < right ; a ++ ) if ( steps[a] > n ) unreach++;
printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cas++,unreach,m,n);
fscanf(input,"%d%d",&m,&n);
}
fscanf(input,"%d",&number);
initialize();
}
system("PAUSE");
return 0;
}
void initialize(){
int i , j ;
for ( i = 0 ; i < right ; i++ ) {
trans[i] = 0;
}
for ( i = 0 ; i < right ; i++ ){
for ( j = 0 ; j < right ; j++ ){
graph[i][j] = ( i == j ) ? 32 : 0 ;
}
}
right = 0;
ini_visit();
}
void ini_visit(){
int i ;
for ( i= 0 ; i < right ; i++ ){
visit[i] = 0 ;
queue[i] = 0 ;
steps[i] = 0;
}
head = 0 ;
tail = 0;
unreach = 0;
}
void connect(int p, int q ){
if ( p != q ){
graph[p][q] = 1;
graph[q][p] = 1;
}
}
void check(int number){
int counter;
for ( counter = 0 ; counter < right ; counter ++ ){
if ( trans[counter] == number ) break;
}
if ( counter == right ) trans[right++] = number;
}
int query(int number){
int counter;
for ( counter = 0 ; counter < right ; counter ++ ){
if ( trans[counter] == number ) return counter;
}
return -1;
}
int is_empty() {
if(head == tail)
return 1;
return 0;
}
int is_full() {
if( (tail + 1)%30 == head )
return 1;
return 0;
}
void enqueue(int number){
if ( !is_full() ){
queue[tail] = number;
tail = ( tail + 1 ) % 30;
}
}
int dequeue(void) {
int value;
if ( !is_empty() ){
value = queue[head];
head = ( head + 1 ) % 30;
}
return value;
}
void BFS(int start_v,int TTL ){
int a,counter,w;
visit[start_v] = 1;
for ( counter = 0 ; counter < right ; counter ++ ) {
if ( graph[start_v][counter] == 1 && visit[counter] == 0 ){
enqueue(counter);
steps[counter] = steps[start_v]+1;
visit[counter] = 1 ;
}
}
while ( !is_empty() ){
w = dequeue();
BFS(w,TTL);
}
}
補充說明： 基本上的精神就是 用一個circular queue 來implement
BFS，uva給的input跑會過，我自己加上的一些edge 例如: 節點連到自己也會過
或著是TTL大於節點數也會過，但是送上去onling judge 還是wa 不得已請各位幫忙指
正哪裡有錯誤，感激不盡 。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.169.217.174