这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1175
BFS,如果用纯BFS会超时,剪枝,增加一个数组rec[][]保存当前点的最小转折点,这样可以剪去很多不必要的路径。
这题很BUG,因为我的int dir[4][2] = {{}, {}, {}, {}}的4个方向顺序不同,时间相差数倍,我用上下左右来写,超时,我找了一个多小时,换了一个方向,结果就只要3000ms了,真是无语了~~~
AC代码:
#include
#include
#include
#include
using namespace std;
const int INF = 99;
int dir[4][2] = \{\{1,0}, {-1,0}, {0,1}, {0,-1\}\}; // up, down, left, right
int n, m, q;
int map[1005][1005]; // 保存输入的值
int rec[1005][1005];
int sx, sy, ex, ey;
bool flag;
typedef struct node{
int x, y;
int turn;
int d;
}node;
node start;
queue que;
inline bool isIn(const node &p;){
if(p.x<1 || p.y<1 || p.x>n || p.y>m)
return false;
return true;
}
void BFS()
{
node now, tmp;
while(!que.empty())
{
now = que.front();
que.pop();
if(now.x == ex && now.y == ey && now.turn <= 2)
{
flag = true;
return;
}
for(int i=0; i<4; ++i)
{
tmp.x = now.x + dir[i][0];
tmp.y = now.y + dir[i][1];
if(now.d == i)
{
tmp.turn = now.turn;
tmp.d = i;
}
else
{
tmp.turn = now.turn + 1;
tmp.d = i;
}
if(isIn(tmp) && (map[tmp.x][tmp.y]==0||tmp.x==ex&&tmp.y;==ey) && rec[tmp.x][tmp.y] >= tmp.turn)
{
rec[tmp.x][tmp.y] = tmp.turn;
que.push(tmp);
}
}
}
}
int main()
{
//freopen("input.txt", "r", stdin);
while(scanf("%d %d", &n;, &m;))
{
if(n == 0 && m == 0)
break;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
scanf("%d", ↦[i][j]);
//cin >> q;
scanf("%d", &q;);
while(q--)
{
//cin >> sx >> sy >> ex >> ey;
scanf("%d %d %d %d", &sx;, &sy;, &ex;, &ey;);
//memset(rec, INF, sizeof(rec));
// 判断两点的值不相同,或其中一点值为0,或者两点是同一点,此时直接判为NO
if((map[sx][sy] != map[ex][ey])
|| (map[sx][sy] == 0)
|| (map[ex][ey] == 0)
|| (sx==ex && sy==ey))
{
cout << "NO\n";
continue;
}
//------------
// 清空队列que
while(!que.empty())
que.pop();
// 初始条件,加入队列que
for(int i=0; i<4; ++i)
{
start.x = sx;
start.y = sy;
start.turn = 0;
start.d = i;
que.push(start);
}
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
rec[i][j] = 11;
flag = false;
rec[sx][sy] = 0;
BFS();
if(flag)
cout << "YES\n";
else
cout << "NO\n";
}
}
return 0;
}