# [FZOJ1554] 大逃亡 (escape.*)

2 5 6
0 0 4 0
2 1
2 3

2 14

## 来源 Source

2014-10-4 NOIP 模拟赛 by lwher

FZOJ 1554

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
int i,j,t,n,m,l,r,k,z,y,x;
int a[1005][1005];
bool used[1005][1005];
deque < pair<int,int> > q;
deque < pair<pair<int,int>,int> > f;
int sx,sy,ex,ey,X,Y;
int ans,step;
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline void floodfill()
{
int i,j,t,tx,ty;
while (!q.empty())
{
for (i=0;i<4;i++)
{
tx=q.front().first+dx[i];ty=q.front().second+dy[i];
if (tx<0 || tx>=X || ty<0 || ty>=Y) continue;
if (a[tx][ty]>a[q.front().first][q.front().second]+1)
{
a[tx][ty]=a[q.front().first][q.front().second]+1;
if (!used[tx][ty])
{
used[tx][ty]=true;
q.push_back(make_pair(tx,ty));
}
}
}
q.pop_front();
}
}
inline bool can(int s)
{
int i,j,t,tx,ty;
while (!f.empty()) f.pop_front();
memset(used,false,sizeof(used));
f.push_back(make_pair(make_pair(sx,sy),0));used[sx][sy]=true;
while (!f.empty())
{
for (i=0;i<4;i++)
{
tx=f.front().first.first+dx[i];ty=f.front().first.second+dy[i];
if (tx==ex && ty==ey)
{
step=f.front().second+1;
return true;
}
if (tx<0 || tx>=X || ty<0 || ty>=Y) continue;
if (a[tx][ty]<s) continue;
if (!used[tx][ty])
{
used[tx][ty]=true;
f.push_back(make_pair(make_pair(tx,ty),f.front().second+1));
}
}
f.pop_front();
}
return false;
}
int main()
{
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
for (i=0;i<X;i++) for (j=0;j<Y;j++) a[i][j]=inf;
memset(used,false,sizeof(used));