用队列解决电路布线问题的代码

不仅能搜索出最短路径长，还能输出具体路径

// Lee‘s wire router

#include 
#include “wire.h“

void InputGrid（Position &start Position &finishint **&gridint &mint &n）
{
   cout << “Enter grid size“ << endl;
   cin >> m >>n;
   while（（m<2&&n<2）||m<1||n<1）
   {
	   cout<<“ERROR!“<	   cout << “Enter grid size“ << endl;
	   cin>>n>>n;
   }

   cout << “Enter start“ << endl;
   cin >> start.row >> start.col;
   cout << “Enter finish“ << endl;
   cin >> finish.row >> finish.col;
   Make2DArray（grid m+2 n+2）;
   cout << “Enter wiring grid“ << endl;//注意障碍赋值1，其他为0
   for （int i=1; i<=m; i++）
	   for （int j=1; j<=n; j++） cin >> grid[i][j];
	// initialize wall of blocks around grid
	for （int a = 0; a <= m+1; a++） 
	   grid[a][0] = grid[a][n+1] = 1; // left and right	   
	for （int b = 0; b <= n+1; b++）
	   grid[0][b] = grid[m+1][b] = 1; // bottom and top
}

bool OutputPath（int PathLen Position *pathint sum）
{// Output wire path.
   cout << “The wire path is“ << endl<<“NO.“<   for （int i=0; i < PathLen+1; i++）
      cout << （path[i]）.row <<“ “<< （path[i]）.col << endl;
   cout<<“next?“<   char c;
   while（cin>>c）
   {
	   if（c==‘Y‘||c==‘y‘）
		   return true;
	   else if（c==‘N‘||c==‘n‘）
		   return false;
	   else
		   cout<<“ERROr!---Y or N“<   }
   return true;
}

void main（void）
{
   Position startfinish;
   int **grid;
   int m n;
   InputGrid（startfinishgridmn）;
   Wire path（gridstartfinishmn）;
   int information=path.FindPath（）;
   if（information==1）//此时无最短路径
	   cout<<“no path“<   else if（information==2）//此时查找出几条路径后，已再无其他最短路径
	   cout<<“no path already!“<   //PS:information为0时是选择不再查找的情况
   //本来FindPath（）这个函数是无返回值的，但是为了把界面的代码全放到main.cpp中只能这样
}
/*
7 7
3 2
4 6
0 0 1 0 0 0 0
0 0 1 1 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 0 0
1 0 0 0 1 0 0
1 1 1 0 0 0 0
1 1 1 0 0 0 0
*/
/*
5 5
2 2
3 3
0 1 1 0 0
0 0 1 0 1
0 1 0 0 0
1 0 0 0 0
0 0 1 1 1
*/
/*
20 20
1 1
1 19
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
*/

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     200743  2010-05-30 09:37  wire队列类结构加强版\wire\Debug\main.exe

     文件    1094620  2010-05-30 09:37  wire队列类结构加强版\wire\Debug\main.ilk

     文件      44599  2010-05-30 09:37  wire队列类结构加强版\wire\Debug\main.obj

     文件    1366124  2010-05-30 09:36  wire队列类结构加强版\wire\Debug\main.pch

     文件     599040  2010-05-30 09:37  wire队列类结构加强版\wire\Debug\main.pdb

     文件      82944  2010-05-30 09:38  wire队列类结构加强版\wire\Debug\vc60.idb

     文件      94208  2010-05-30 09:37  wire队列类结构加强版\wire\Debug\vc60.pdb

     文件       2246  2010-05-25 19:30  wire队列类结构加强版\wire\lqueue.h

     文件       2898  2010-05-30 09:37  wire队列类结构加强版\wire\main.cpp

     文件       3436  2010-05-30 09:38  wire队列类结构加强版\wire\main.dsp

     文件        533  2010-05-30 09:38  wire队列类结构加强版\wire\main.dsw

     文件      50176  2010-05-30 09:38  wire队列类结构加强版\wire\main.ncb

     文件      48640  2010-05-30 09:38  wire队列类结构加强版\wire\main.opt

     文件       1119  2010-05-30 09:37  wire队列类结构加强版\wire\main.plg

     文件        311  2010-05-25 19:30  wire队列类结构加强版\wire\make2db.h

     文件        249  2010-05-25 19:30  wire队列类结构加强版\wire\node.h

     文件       3439  2010-05-25 19:30  wire队列类结构加强版\wire\wire.cpp

     文件       4260  2010-05-28 13:26  wire队列类结构加强版\wire\wire.dsp

     文件        531  2010-05-28 13:26  wire队列类结构加强版\wire\wire.dsw

     文件       3919  2010-05-30 09:36  wire队列类结构加强版\wire\wire.h

     文件      33792  2010-05-28 13:26  wire队列类结构加强版\wire\wire.ncb

     文件      48640  2010-05-28 13:26  wire队列类结构加强版\wire\wire.opt

     文件       1029  2010-05-25 20:13  wire队列类结构加强版\wire\xcept.h

     目录          0  2010-05-30 09:37  wire队列类结构加强版\wire\Debug

     目录          0  2010-05-30 09:38  wire队列类结构加强版\wire

     目录          0  2010-05-30 09:04  wire队列类结构加强版

----------- ---------  ---------- -----  ----

              3687496                    26