1771: 最少经过几个城市（例题）
Time Limit: 1.000 Sec Memory Limit: 128 MBSubmit: 769 Solved: 457
[Submit] [Status] [Web Board] [Creator:]
Description
图8-2表示的是从城市1到城市8的交通图。从图中可以看出，从城市1到城市8要经过若干个城市。最少经过几个城市，包括开始城市和结束城市。1表示能走，0表示不能走
Sample Input
0 1 1 1 0 1 0 0
1 0 0 0 0 1 0 0
1 0 0 1 1 0 0 0
1 0 1 0 0 0 1 0
0 0 1 0 0 0 1 1
1 1 0 0 0 0 0 1
0 0 0 1 1 0 0 1
0 0 0 0 1 1 1 0Sample Output
3HINT
#include<bits/stdc++.h>
using namespace std;
int main() {
int t,h,a[9][9],bs[101]={0},b[101]={0},q[101]={0};
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
cin>>a[i][j];
}
}
bs[1]=1;
b[1]=1;
q[1]=1;
t=1;
h=0;
while(h<t) {
h++;
for(int i=1;i<=8;i++){
if(a[q[h]][i]==1&&b[i]==0){
t++;
q[t]=i;
bs[i]=bs[q[h]]+1;
b[i]=1;
if(q[i]==8){
cout<<bs[i];
break;
}
}
}
}
return 0;
}
using namespace std;
int main() {
int t,h,a[9][9],bs[101]={0},b[101]={0},q[101]={0};
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
cin>>a[i][j];
}
}
bs[1]=1;
b[1]=1;
q[1]=1;
t=1;
h=0;
while(h<t) {
h++;
for(int i=1;i<=8;i++){
if(a[q[h]][i]==1&&b[i]==0){
t++;
q[t]=i;
bs[i]=bs[q[h]]+1;
b[i]=1;
if(q[i]==8){
cout<<bs[i];
break;
}
}
}
}
return 0;
}