函數(shù)和上界函數(shù)等必要的函數(shù),并將此函數(shù)用于解布線問題.

印刷電路板將布線區(qū)域劃分成n×m個方格陣列(見圖6-3(a)).精確的電路布線問題要求確定連接方格a的中點到方格b的中點的最短布線方案.在布線時,電路只能沿直線或直角布線(見圖6-3(b).為了避免線路相交,已布線了的方格做了封鎖標(biāo)記,其他線路不允許穿過被封鎖的方格.

算法設(shè)計:對于給定的布線區(qū)域,計算最短布線方案.

數(shù)據(jù)輸入:由文件input.txt給出輸入數(shù)據(jù).第1行有3個正整數(shù)n、m、k,分別表示布線區(qū)域方格陣列的行數(shù)、列數(shù)和封閉的方格數(shù).接下來的k行中,每行2個正整數(shù),表示被封閉的方格所在的行號和列號.最后的2行,每行也有2個正整數(shù),分別表示開始布線的方格(p,q)和結(jié)束布線的方格(r,s).

結(jié)果輸出:將計算的最短布線長度和最短布線方案輸出到文件output.txt.文件的第1行是最短布線長度.從第2行起,每行2個正整數(shù),表示布線經(jīng)過的方格坐標(biāo).如果無法布線,則輸出“NoSolution!”.