[挑战]查询北京地铁线路

随风

也考虑过坐标，可是批处理不知道如何弄啊
现在是获取出发点的车次到目的地的车次，只要在交接点中查询就可以了
call 在语句块中递归，能最终找到目的，但无法正确计算途中经过的节点，抓狂中。。

CrLf

用坐标如何保证站点之间遵循严格的几何形呢？看上去是正方形的路线难免不会出现上底下底站点数不一样的情况。

现在的想法是双向递归，从两点开始层层遍历（就像小时候走复杂的迷宫一样），直到可行的路线相互碰撞，不过说起来容易，做起来...

batman

我在看此题时写了一个步骤：

首先找出节点站  一级 二级 三级。。。同时将线路和站点均设为变量

1、先打本线路上是不是有这个站 有a-b 没有向下

2、确定目的站在哪条或哪几条线上

3、查找本线路上哪个站在这些线路上 列出所有a-c-b 没有向下

4、查找本线路上所有的节点站 找出这些节点站所在线路的其他节点站是否在目的站所在线路上 a-c-d-b 再没有（四次换乘）脑子不够用了。。。

plp626

我目前对于通用模型没有思路，以下资料有感兴趣的可以参考下：
http://jpkc.cug.edu.cn/08jpkc/pengfang57/bigclass/09/lw/028.htm

http://download.csdn.net/source/1056130/

http://download.csdn.net/source/1710561

http://slcx.sci.bupt.cn/sxjm/paper/source/cumcm2007/cumcm0747.PDF

http://wenku.baidu.com/view/857e4cc5bb4cf7ec4afed04a.html

http://jsj.sict.edu.cn/jpkc/dotnet/jxzy/BS/gjcx/PPT/gjxz06.ppt

523066680

我勒个去，这就是一个草...马



                                                                                   ,,,,,,,,,,,,,,,,,,,,,,,,.
                                                                                  Gr;.sr.rr.rr.rr.rs,;s:,sr
                                                                                 S@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 ;B                        
                              ..      .             ..  .                        S@                        
                         .@#@@BH@@A#@#A@@BB@@A#@#A@@@@@MH@#H@#A@#A@#A@@A@@@@@@BA#@@;                        
                        B@s                                                      ;@#@:                     
                      S@A                                                           ;@@                     
                    @                                                               3@S                  
                   @@                                                                   @r                  
                 3@X                                                                    @s                  
               ;@@                                                                      @r                  
             ,#@,                                                                       @s                  
            H@r                                     .                                   @r                  
          i@B                                       @A                          .#i     @s                  
        :@@                                         @B                        s@@@@     @;                  
       #r:                        .. . .. .  ... .; @@   ..  ...  ...      i@@#: r@  .  @5                  
     5@3                     MH3A3hAGAh3A9G&GA99&&@h@@rSX&&X29Ah229&h2ssH@@@#r,;;M@rX952@M5hi               
   :@X                       #                      GS                rMMr       ;@                        
  @@2 ,;;:          ;ssrrsr:,@2:;;;;;:;;:;;:;;:;;;r:@@,:;:;;;;:;;;;;A@9.         r#                        
  3is2&2r;          rhhS23r2@HXSXSS35iX2i22i2Xi22XA2@@rSXiSX2Xi5X5XS;            s#                        
                          ;2.                       92                           i@                        
                        ;Hi                         H3                           s@                        
                      ,#X                           &5                           5@                        
                     AB.                            @&                           :r                        
                   S#;                              #A                                                      
                 ;M2                                @H                                                      
               .&H,                                 ::                                                      
              5#r                                                                                          
            r@5                                                                                             
          ,MA                                                                                               
        .A#:                                                                                                
       .;.                                                                                                  

caruko

其实 这个算法 类似 路由器的 距离向量路由算法，当然还有更高级的链路状态协议，生成树等等。

caruko

=。= 前面得出的线路基本正确，但是发现根据路线计算出站点数更烦琐。
虽然算法不难。

随风

总算搞出来了，基本符合要求，复杂路线还没测试.

@echo off&setlocal enabledelayedexpansion
for /f "tokens=1* delims= " %%i in (dt.txt) do (
    set max=0
    for %%a in (%%j) do (
         set xian.%%i=!xian.%%i! %%a
         if defined zan.%%a set jie.%%a=!zan.%%a! %%i
         set zan.%%a=!zan.%%a! %%i
         set /a max+=1
         set /a ###%%i.%%a=!max!
    )
)
:: 获取所有线上的节点站名
for /f "tokens=2,3 delims=.=" %%i in ('set jie.') do (
    for %%a in (%%j) do set #%%a=!#%%a! %%i
)
:start
setlocal&cls
set /p xxx=输入起点站和终点站如: 华强路 岗厦北
for /f "tokens=1,2 delims= " %%a in ("!xxx!") do (
    set qix=!zan.%%a!&set "zx=!zan.%%b!"
    set qidian=%%a&set "zongdian=%%b"
    for %%i in (!zan.%%b!) do set zd.%%i=%%i
)
echo !qidian! --- !zongdian!     !qix!  ---  !zx!
echo;.............................................&echo;
:: 判断是否在同一条线
for %%a in (!qix!) do (
    for %%b in (!zx!) do if "%%a"=="%%b" (
        set tong=!tong! %%a
        call :tong !qidian! !zongdian!
        echo !ok!  共 !zzu! 站
        echo;.............................................
    )
)
if defined tong echo;&pause&endlocal&goto :start
rem        起点线    终点线  
call :kai "!qix!"
for /f "tokens=1* delims==" %%i in ('set $') do (
    set "%%i="&set /a mmm=0
    set tong=!qix!&set L1=!qidian!
    for %%k in (%%j) do (
        for /f "tokens=1,2 delims=/" %%a in ("%%k") do (
            set num=%%a&set tong2=%%b
        )
        call :tong !L1! !num!
        set /a mmm+=zzu,%%i+=1
        set tong=!tong2!&set L1=!num!
        echo            !ok! !zzu! 站
    )
    set tong=!zx!
    call :tong !num! !zongdian!
    set /a mmm+=zzu&set "mmm=  !mmm!"
    echo 累计!mmm:~-3!站  !ok! !zzu!站              
    echo;.............................................&echo;
)
echo;&pause&endlocal&goto :start
:kai
for %%a in (%~1) do (
    set t.%%a=a
    for %%b in (!#%%a!) do (rem %%b为%%a线上的节点站名
        for %%c in (!jie.%%b!) do (rem %%c为节点站上的线名
            if not defined t.%%c (
                if not defined zd.%%c (
                    set @=!@! %%b/%%c
                    call :kai "%%c"
                    set "t.%%c="
                    set @=!@: %%b/%%c=!
                    ) else (
                        set /a fl.+=1
                        set $!fl.!=!@! %%b/%%c
                )
            )
        )
    )
)
goto :EOF
:tong
for %%a in (!tong!) do (
    set strq=!###%%a.%1!
    set strz=!###%%a.%2!
    set /a zzu=strq-strz
    set zzu=!zzu:-=!
    set ok=%%a/%1 --- %%a/%2
)
goto :EOF
复制代码

随风

已在顶楼更新北京地铁

随风

经验证11楼的比我23楼的精确百倍，也高效百倍..

mxxcgzxxx

如果把换乘站点独立开来只看做一条线路中的一个节点，如：422  502   都是布吉
将路线拉直看做一个大函数以进行正向计算，如：
龙岗（5 16 1 422）表示：龙岗是线路5，16个站点，1个换乘点，1号换乘点通向422（4路22号）
环中（4 27 2 502 228）表示：环中4号线，27站点，2个换乘点，1号502 ，2号228
这样行不行？

batman

23# 随风
if defined zan.%%a set jie.%%a=!zan.%%a! %%i
set zan.%%a=!zan.%%a! %%i
这两句可以合为一句吧：set zan.%%a=!zan.%%a! %%i

caruko

=.= 我就解释一下我的算法吧。。。

第一步： 统计各个站点出现的次数，>=2的是交点。
第二步： 统计每个交点连接哪几条线路。 比如 @世界之窗=蛇口线 罗宝线
第三步： 计算 起点-终点 是否在一条线上，可直达。

换乘的算法：
假如：
起点 在 A 线路上
A线路 ∈ X交点集合(包含能直接到达的线路)
:loop
"X交点（除去A线路） ∩ 除X以外的剩余交点" ， 同时计算"X ∩ 终点"是否成立，成立则退出循环返回结果。
如果 X  跟 Y  相交（就是Y交点含有X交点中的线路）
"Y 交点(除去跟X相交的站点) ∩ 除XY以外的交点" ，  计算 "Y ∩ 终点" 是否成立。
goto :loop

caruko

总的来说，就是计算 各个集合之间 相交，相异 的结果。

caruko

这是完善版本，默认只输出换乘次数最少的路线。要得到更多换乘次数的路线，注释掉49行。

可输出多个： 路线  换乘次数 途经站点数

@ECHO OFF&SETLOCAL ENABLEDELAYEDEXPANSION
set /p input=请输入起点站-终点站:
for /f "tokens=1,2 delims=-, " %%a in ("!input!") do set "start=%%a"&set "end=%%b"
::取得交点。
for /f "tokens=1* delims= " %%a in (dt.txt) do (
    set "xl_%%a=%%b"
    for %%i in (%%b) do set /a #%%i+=1
)
for /f "tokens=1,2 delims=#=" %%a in ('set #') do (
    if !#%%a! geq 2 set "dd_list=!dd_list! %%a"
    set "#%%a="
)
::取得每个交点可到达的线路。
for /f "tokens=2,3 delims=_=" %%a in ('set xl_') do (
    set "str=%%b"
    for /f "tokens=1,2" %%x in ("!start! !end!") do (
        if not "!str:%%x=#!"=="!str!" set "start_xl=!start_xl! %%a"
        if not "!str:%%y=#!"=="!str!" set "end_xl=!end_xl! %%a"
    )
    for %%D in (!dd_list!) do (
        if not "!str:%%D=!"=="!str!" (
            set "%%x=!%%x:%%D=@%%D!"
            set "@%%D=!@%%D! %%a "
)))
::检查是否可直达
for %%a in (!start_xl!) do for %%b in (!end_xl!) do if %%a==%%b set "路线=^"!start! !end!^""
if not "!路线!"=="" goto :metic
::计算换乘路线
set "查询表=^"!start!=!start_xl!^""
set "剩余交点表=!dd_list!"
:loop
for %%i in (!查询表!) do (
for /f "tokens=1* delims==" %%A in ("%%~i") do (
for %%a in (%%B) do (
    for %%b in (!剩余交点表!) do (
        for %%c in (!@%%b!) do (
            if %%a==%%c (
                set "转车点=!转车点! %%b"
                set "剩余查询表=!剩余查询表! ^"%%A %%b=!@%%b:%%c=!^""
                for %%d in (!end_xl!) do for %%e in (!@%%b!) do if %%e==%%d (
                    set "路线=!路线! ^"%%A %%b !end!^" "
)))))))
for %%a in (!剩余交点表!) do for %%b in (!转车点!) do set "剩余交点表=!剩余交点表:%%b=!"
set "查询表=!剩余查询表!"
set "剩余查询表="
set 最多换乘次数+=1
rem if !最多换乘次数! geq 5 goto :metic
rem 注释掉下面这句，使用上面这句可以找到更多换乘次数的路线。
if !路线!.==. goto :loop
::计算站点
:metic
if !路线!.==. echo,无法找到换乘路径&goto :eof
set /a xn=0
for %%a in (!路线!) do (
    set /a xn+=1
    set "线路_!xn!=%%~a"
    set "now="
    set "last="
    set /a 换乘次数_!xn!=0
    for %%a in (%%~a) do (
        set /a 换乘次数_!xn!+=1
        if defined now set "last=!now!"
        set "now=%%a"
        if defined last call :js !xn! !last! !now!
    )
    set /a 换乘次数_!xn!-=2
)
for /l %%i in (1,1,!xn!) do echo,线路%%i:"!线路_%%i: =--!"，换乘 !换乘次数_%%i! 次，途经 !num_%%i! 站
goto :eof
:js
for /f "tokens=1,2 delims==" %%a in ('set xl_') do (
    set "xl=%%b"
    if not "!xl:%2=!"=="!xl!" if not "!xl:%3=!"=="!xl!" (
        set /a n=0
        for %%x in (%%b) do (
            set /a n+=1
            if %%x.==%2. set /a st=n
            if %%x.==%3. set /a et=n
        )
        set /a num=st-et
        if !num! lss 0 set /a num=0-num
        set /a num_%1+=num
)   )
复制代码

请输入起点站-终点站:奥体中心 西直门
线路1:"奥体中心--北土城--海淀黄庄--西直门"，换乘 2 次，途经 12 站
线路2:"奥体中心--北土城--知春路--西直门"，换乘 2 次，途经 7 站
线路3:"奥体中心--北土城--芍药居--西直门"，换乘 2 次，途经 16 站
复制代码