# 搜寻4-noi6264:走出迷宫

www.MyException.Cn  网友分享于：2013-08-16  浏览：0次

# 搜索4--noi6264:走出迷宫

## 6264:走出迷宫

1000ms

65536kB

```3 3
S#T
.#.
...```

`6`

```  1 //6264:走出迷宫
2 #include <iostream>
3 #include <queue>
4 using namespace std;
5 //n表示行，m表示列
6 int n,m;
7 //上右下左
8 int runRow[4]={1,0,-1,0};
9 int runColumn[4]={0,1,0,-1};
10 //迷宫
11 char maze[105][105];
12 //起点和终点
13 int startR,startC,endR,endC;
14 //描述点的结构体
15 struct node{
16     int row;//行
17     int column;//列
18     int minStep;//到每个点的最短步数
19 };
20 //每个点是否被访问
21 bool vis[105][105];
22
23 queue<node> mazeQueue;
24
25 void readData(){
26     cin>>n>>m;
27     for(int i=1;i<=n;i++){
28         for(int j=1;j<=m;j++){
29             cin>>maze[i][j];
30             //找到起点和终点
31             if(maze[i][j]=='S'){
32                 startR=i;
33                 startC=j;
34             }else if(maze[i][j]=='T'){
35                 endR=i;
36                 endC=j;
37             }
38         }
39     }
40 }
41
42 void printMaze(){
43     for(int i=1;i<=n;i++){
44         for(int j=1;j<=m;j++){
45             cout<<maze[i][j]<<" ";
46         }
47         cout<<endl;
48     }
49     cout<<"start:"<<startR<<"."<<startC<<endl;
50     cout<<"end:"<<endR<<"."<<endC<<endl;
51 }
52
53 void search(int startR,int startC){
54     node *p=new node;
55     //设置起点
56     p->row=startR;
57     p->column=startC;
58     p->minStep=0;
59     //把起点添加至队列
60     mazeQueue.push(*p);
61     vis[startR][startC]=true;
62     //访问所有点的可能情况
63
64     while(!mazeQueue.empty()){
65         node q=mazeQueue.front();
66         mazeQueue.pop();
67 //        cout<<"node: "<<q.row<<" "<<q.column<<" "<<q.minStep<<endl;
68 //        cout<<"------------------------------------------------"<<endl;
69 //        cout<<"q.row: "<<q.row<<"q.column: "<<q.column<<endl;
70 //        cout<<"endR: "<<endR<<"endC: "<<endC<<endl;
71 //        cout<<"------------------------------------------------"<<endl;
72         if(q.row==endR&&q.column==endC){
73             cout<<q.minStep<<endl;
74             break;
75         }else{
76             for(int i=0;i<=3;i++){
77                 int row1=q.row+runRow[i];
78                 int column1=q.column+runColumn[i];
79
80                 if(row1>=1&&row1<=n&&column1>=1&&column1<=m&&(maze[row1][column1]=='.'||maze[row1][column1]=='T')&&!vis[row1][column1]){
81 //                    cout<<"row1: "<<row1<<"column1: "<<column1<<endl;
82                     vis[row1][column1]=true;
83                     node *p1=new node;
84                     p1->row=row1;
85                     p1->column=column1;
86                     p1->minStep=q.minStep+1;
87                     mazeQueue.push(*p1);
88                 }
89             }
90         }
91
92     }
93
94 }
95
96 int main(){
97     //freopen("in.txt","r",stdin);
98     readData();
99     search(startR,startC);
100     //printMaze();
101     return 0;
102 }```

1、迷宫中不只为'.'的可以走，为‘T’的也可以走

2、基于第一点，所以可以优化代码，所有按照能不能走来来标识为true或者false