[暴力][BFS][最短路][复杂度分析] codeforces 1064D Labyrinth

http://codeforces.com/contest/1064/problem/D

这个题最操蛋的是我把复杂度弄错了导致没有敢写暴力。。不过官方并没有出题解所以我也不知道我的做法是否可行，只能说通过了目前的所有数据。

做的思路就是求出来原点到每个点所用的最小的left和最小的right，求的方法就是暴力bfs，但是这里有个问题是有可能会有一个点可以通过多条路径到达，那么该如何确定最小值？如果直接裸搜不打标记会使得无限循环，如果打标记则会使得多种可能没有考虑，我这里用了一个玄学剪枝就是当当前点的下一个点的数据有被更新的时候才加到queue里，否则就不加，可以保证去掉了很多无用的扩展也可以保证搜索可以结束。另外一个优化是加了点是否已经在queue内的判断，可以避免多余的入队操作（这个貌似也可以用在一般的dij里啊）

#include

using namespace std;
typedef long long LL;
const int maxn=2e3+4;
const int mod=998244353;
const int INF=0x3f3f3f3f;

char board[maxn][maxn];
int dp[maxn][maxn][2];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int n,m,r,c,lm,rm;
bool check(int x,int y)
{
    return 0 > Q;
    pair cur;
    Q.push(make_pair(r,c));
    inq[r]=1,dp[r][0]=dp[r][1]=0;
    int cx,cy,nx,ny,pl,pr;
    while(!Q.empty())
    {
        cur=Q.front();Q.pop();
        cx=cur.first,cy=cur.second;
        inq[cx][cy]=0;
        for(int i=0;i<4;i++)
        {
            nx=cx+dx[i],ny=cy+dy[i];
            if(check(nx,ny))
            {
                pl=dp[nx][ny][0],pr=dp[nx][ny][1];
                dp[nx][ny][0]=min(dp[nx][ny][0],dp[cx][cy][0]+(i==3));
                dp[nx][ny][1]=min(dp[nx][ny][1],dp[cx][cy][1]+(i==1));
                if(!inq[nx][ny]&&(pl>dp[nx][ny][0]||pr>dp[nx][ny][1]))//玄学剪枝
                {
                    Q.push(make_pair(nx,ny));
                    inq[nx][ny]=1;
                }

            }
        }
    }
}

int main()
{
    cin>>n>>m;
    cin>>r>>c;
    cin>>lm>>rm;

    for (int i=1;i<=n;i++)
        cin>>(board[i]+1);
    Dij();
    int ans=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
    {
        if(dp[i][j][0]<=lm&&dp[i][j][1]<=rm)
            ans++;
    }
    cout<