[UVA 208]Firetruck(양 방향 검색)
제목 링크:http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=17347
제목 의 대의:
소방 차 는 출발점 1 에서 출발 하여 종점 n 까지 간다.몇 개의 경로 가 있 는 지 물 어보 고 경 로 를 사전 순서에 따라 출력 합 니 다.
우선 무방 향도 이 고 결점 수 는 최대 21 이다.
다음 과 같은 예:
4.567913.6 은 불 이 난 곳 이 고 8 개의 길이 있 으 며 길 은(0,0)로 끝난다.출력 사례 는 다음 과 같 습 니 다.
6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0문제 풀이 방향:
처음에는 출발점 부터 거 슬러 올 라 가 dfs 심 사 를 했 지만 TLE 는.......................................................좋 은 해결 방안 을 생각 하지 못 하고 다른 사람의 문제 해결 보고 서 를 보고 좋 은 생각 이 있 습 니 다.쌍방 향 검색 입 니 다.
종점 부터 BFS 를 진행 하고 도착 할 수 있 는 모든 결점 을 1 use 배열 로 표시 하 는 것 이다.
그 다음 에 출발점 부터 DFS 역 추적 을 통 해 심층 검색 을 하 는데 기 존 에 표 시 된 것 이 고 조건 에 맞 는 것 만 검색 할 수 있어 효율 을 크게 높 였 다.
코드:
CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령제1 6 장 파일 에서 텍스트 검색 도구: grep 명령 과 egrep 명령 옵션 grep 명령 파일 에서 단 어 를 검색 하면 명령 은 "match pattern"을 포함 하 는 텍스트 줄 을 되 돌려 줍 니 다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
