그림 구조 연습 - BFS - 시작 점 에서 목표 점 까지 의 최 단 걸음 수
오래된 마수 전설 에 의 하면 두 개의 군단 이 있 는데 하 나 는 천재 이 고 하 나 는 근 위 라 고 한다.그들 이 있 는 지역 에는 n 개의 요충지 가 있 고 번 호 는 1. n 이 며 어떤 요충지 사이 에는 통로 가 연결 되 어 있다.그 중에서 근위군 단 은 1 번 요새 에 있 고 천재 군단 은 n 번 요새 에 있다.어느 날, 천재지변 군단 의 지도자 인 요괴 왕 은 근 위 군단 을 공격 하기 로 결 정 했 습 니 다. 천재지변 군단 의 부 대 는 이렇게 거대 해서 강 을 메 워 강 을 건 널 수도 있 습 니 다.그러나 요괴 왕 은 불필요 한 대 가 를 치 르 고 싶 지 않 았 다. 그 는 어떤 통 로 를 건설 하지 않 는 전제 에서 부대 가 요새 와 관련 통 로 를 통 해 근위군 단 에 도착 하여 공격 할 수 있 는 지 알 고 싶 었 다.가능 하 다 면 최소한 몇 개의 통 로 를 거 쳐 야 합 니까?n 의 값 이 비교적 크기 때문에 (n < = 1000) 요괴 왕 은 프로 그래 밍 을 잘 하 는 당신 을 찾 았 습 니 다 = =,당신 이 그 를 도와 이 문 제 를 해결 해 주세요. 그렇지 않 으 면 당신 을 잡 아 먹 는 것 이 그의 마법 이 될 것 입 니 다.자신 을 구하 기 위해 서 빨리 방법 을 생각해 보 세 요.
입력
여러 그룹 을 포함 하 는 입력 을 하 십시오. 각 그룹의 형식 은 다음 과 같 습 니 다.
첫 번 째 줄 은 두 개의 정수 n, m 를 포함한다.
아래 m 줄 마다 두 개의 정수 a, b 를 포함 합 니 다.a 에서 출발 하여 b 목 에 도달 하 는 통로 가 있 음 을 나타 낸다.
출력
만약 천재지변 군단 이 어떠한 통로 도 건설 하지 않 고 1 번 요새 에 도착 할 수 있다 면, 수출 은 적어도 몇 개의 통 로 를 거 쳐 야 하 며, 그렇지 않 으 면 수출 NO.
예제 입력
2 1
1 2
2 1
2 1예제 출력
NO
1
제시 하 다.
#include <stdio.h>
#include <string.h>
int map1[1002][1002], visit[2000];
struct node
{
int x, ans;
} q[2000];
void bfs(int i, int n)
{
int s=1, e=1, j;
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
",f1.ans);
return ;
}
for(j=1; j<=n; j++)
{
f2.x=j;
if(!visit[f2.x]&&map1[f1.x][f2.x])
{
visit[f2.x]=1;
f2.ans=f1.ans+1;
q[s++]=f2;
}
}
}
printf("NO
");
return ;
}
int main()
{
int n, m, i, j, 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;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
