abc.zip_ABC_布线问题

#include <iostream> #include<stdio.h> using namespace std; typedef struct { int row ; int col ; }Position; typedef struct { //struct Position; int row[10000] ; int col[10000] ; int end; int begin ; }Queue; int grid[100][100]; Position start, finish; int PathLen = 0; Position * path; int n , m , a , b , x ; bool FindPath(Position start,Position finish) {//计算从起点位置start到目标位置finish的最短布线路径，找到最短布线路//径则返回true，否则返回false if((start.row==finish.row) && (start.col==finish.col)) { PathLen=0; return true; } //start=finish //设置方格阵列“围墙” int i ; for( i=0; i<= m+1; i++) grid[0][i]=grid[n+1][i]=1; //顶部和底部 for( i=0; i<= n+1; i++) grid[i][0]=grid[i][m+1]=1; //左翼和右翼 int j ; //初始化相对位移 Position offset[4]; offset[0].row=0; offset[0].col=1;//右 offset[1].row=1; offset[1].col=0;//下 offset[2].row=0; offset[2].col=-1;//左 offset[3].row=-1; offset[3].col=0;//上 int NumOfNbrs=4;//相邻方格数 Position here,nbr; here.row=start.row; here.col=start.col; grid[start.row][start.col]=2; //标记可达方格位置 //LinkedQueue<Position> Q; Queue Q ; Q.end = 0 ; Q.begin = 0 ; do {//标记相邻可达方格 for( i=0; i<NumOfNbrs; i++) { nbr.row=here.row + offset[i].row; nbr.col=here.col+offset[i].col; if(grid[nbr.row][nbr.col]==0) { //该方格未被标记 grid[nbr.row][nbr.col]=grid[here.row][here.col]+1; if((nbr.row==finish.row) &&(nbr.col==finish.col)) break; //完成布线 //Q.Add(nbr); Q.col[Q.end] = nbr.col; Q.row[Q.end] = nbr.row; Q.end++; } } //是否到达目标位置finish？ if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成布线 //活结点队列是否非空？ if(Q.begin==Q.end) return false;//无解 else { here.row=Q.row[Q.begin]; here.col=Q.col[Q.begin]; Q.begin++;//取下一个扩展结点 } }while(true); //构造最短布线路径 PathLen=grid[finish.row][finish.col]-2; path=new Position[PathLen]; //从目标位置finish开始向起始位置回溯 here=finish; for( j = PathLen-1; j>=0; j--){ path[j]=here; //找前驱位置 for( i=0; i<NumOfNbrs; i++){ nbr.row=here.row+offset[i].row; nbr.col=here.col+offset[i].col; if(grid[nbr.row][nbr.col]==j+2) break; } here=nbr;//向前移动 } return true; } int main() { int j ; printf("输入电路板区域n*m和封锁的格数x:\n"); cin>>n>>m>>x; printf("输入封锁的坐标:\n"); for( a = 0 ; a < n+2 ; a ++ ) for( b = 0 ; b < m +2 ; b ++ ) grid[a][b] = 0 ; for( x = x ; x >= 1 ; x -- ) { cin >> a >> b ; grid[a][b]= 1; } printf("输入起始位置和结束位置:\n"); cin>>start.row>>start.col>>finish.row>>finish.col; if(FindPath(start,finish)) { printf("输出路径长度及途中坐标:"); cout<<PathLen<<endl; cout<<start.row<<" "<< start.col<<endl; for( j = 0 ; j < PathLen ; j++ ) cout<<path[j].row<<" "<<path[j].col<<endl; } else cout<<"No Solution!"<<endl; delete []path; return 0 ; }