1.链接地址：
http://bailian.openjudge.cn/practice/2790/
2.题目：
- 总时间限制:
- 3000ms
- 内存限制:
- 65536kB
- 描述
- 一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上 下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则 看成无法办到。
- 输入
- 第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
- 输出
- k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
- 样例输入
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0- 样例输出
NO
3.思路：广搜，注意起点和终点如果不通则直接为NO
4.代码：
#include <iostream>
#include <cstdio>
#include <queue> using namespace std; struct POINT
{
int x;
int y;
}; int idx_x[] = {-,,,};
int idx_y[] = {,,,-}; int main()
{
//freopen("C://input.txt","r",stdin); int i,j; int k;
cin >> k; while(k--)
{
int n;
cin >> n; bool **arr = new bool*[n];
for(i = ; i < n; ++i) arr[i] = new bool[n]; char ch;
for(i = ; i < n; ++i)
{
for(j = ; j < n; ++j)
{
cin >> ch;
if(ch == '.') arr[i][j] = true;
else arr[i][j] = false;
}
} int ha,la,hb,lb;
cin >> ha >> la >> hb >> lb; if(arr[ha][la] == false || arr[hb][lb] == false) {cout << "NO" << endl; continue;}
queue<POINT> q_point;
POINT point;
point.x = la;
point.y = ha;
q_point.push(point);
arr[point.y][point.x] = false; bool flag = false;
while(!q_point.empty())
{
point = q_point.front();
q_point.pop();
for(i = ; i < ; ++i)
{
POINT p2;
p2.x = point.x + idx_x[i];
p2.y = point.y + idx_y[i]; if(p2.y == hb && p2.x == lb) {flag = true;break;}
else if(p2.x >= && p2.x < n && p2.y >= && p2.y < n && arr[p2.y][p2.x])
{
q_point.push(p2);
arr[p2.y][p2.x] = false;
}
}
if(i < ) break;
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl; for(i = ; i < n; ++i) delete [] arr[i];
delete [] arr;
} return ;
}