前一阵子搞教材和其他事情，把博客给落下了。最近趁着找题目的机会，再争取多记录点博客题目。
每日一题最近不能按顺序了，找题目优先了。只能先这样了。

题目描述：
有两个人分别地图上的两个位置，现在两个人要相遇，问最短时间。一个人走8个方向每次一步，另一个走4个方向每次两步。(n,m<=1000)

思路：
经典bfs问题。
两个人相遇问题，显然一个比较常用的方法是离线处理。
先bfs第一个人，记录下他到每个点的最少时间。
接着bfs第二个人，也记录到每个点的最少时间。
那么如果两人能在某个点相遇，相遇时间就是两人中时间大的那个。最后枚举所有的点，找一个最小的值。
注意走两步的处理，在下面的代码中我处理成了走一步花0.5秒，最后计算的时候向上取整。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,v[2][1003][1002];
double d[2][1003][1004],pd;
char s[1004][1004];
pair<int,int>p[2];
int dir[][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};
struct node{
    int x,y;
    double step;
};
bool check(int a,int b){
    if(s[a][b]=='#')return false;
    return true;
}
void bfs(int w){
    queue<node>qu;
    node tmp;
    tmp.x=p[w].first;tmp.y=p[w].second;
    tmp.step=0;
    qu.push(tmp);
    v[w][tmp.x][tmp.y]=1;
    while(qu.size()){
        node now=qu.front();
        qu.pop();
        for(int i=0;i<(w?4:8);i++){
            node tmp;
            tmp.x=now.x+dir[i][0];
            tmp.y=now.y+dir[i][1];
            tmp.step=now.step+1;
            if(w){
                tmp.x=now.x+dir[i][0];
                tmp.y=now.y+dir[i][1];
                tmp.step=now.step+0.5;
            }

            if(s[tmp.x][tmp.y]=='#')continue;
            if(v[w][tmp.x][tmp.y])continue;
            v[w][tmp.x][tmp.y]=1;
            d[w][tmp.x][tmp.y]=tmp.step;
            qu.push(tmp);
        }
    }
}
int main()
{
    cin>>n>>m;
    getchar();
    for(int i=1;i<=n;i++){
        string ts;
        getline(cin,ts);
        int cnt=0;
        for(int j=0;j<ts.size();j++){
            if(ts[j]!=' ')s[i][++cnt]=ts[j];
        }
    }
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            if(i==0||j==0||i==n+1||j==m+1)s[i][j]='#';
            if(s[i][j]=='C')p[0]=make_pair(i,j);
            if(s[i][j]=='D')p[1]=make_pair(i,j);
        }
    }
    bfs(0);
    bfs(1);
    int ans=1e7+7;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#')continue;
            if(!v[0][i][j]||!v[1][i][j])continue;
            ans=min(ans,max(int(d[0][i][j]),int(d[1][i][j]+0.5)));
        }
    }
    if(ans==1e7+7)cout<<"NO"<<endl;
    else
    cout<<"YES"<<endl<<ans<<endl;
    return 0;
}

方法二：
用双向广搜。双向广搜思路是从两个地方分别开始广搜，每次只扩展一层。然后判断是否能在当前层相遇，如果相遇了就可以退出了。这里处理两步的做法是分成2次1步走，扩展到同一层。即做第二个人每次做2次bfs。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,v[2][1003][1002];
double d[2][1003][1004];
char s[1004][1004];
pair<int,int>p[2];
int dir[][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};
struct node{
    int x,y;
    double step;
};
bool check(int a,int b){
    if(s[a][b]=='#')return false;
    return true;
}
queue<node>q1,q2;
int main()
{
    cin>>n>>m;
    getchar();
    for(int i=1;i<=n;i++){
        string ts;
        getline(cin,ts);
        int cnt=0;
        for(int j=0;j<ts.size();j++){
            if(ts[j]!=' ')s[i][++cnt]=ts[j];
        }
    }
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            if(i==0||j==0||i==n+1||j==m+1)s[i][j]='#';
            if(s[i][j]=='C')p[0]=make_pair(i,j);
            if(s[i][j]=='D')p[1]=make_pair(i,j);
        }
    }
    node tmp;
    tmp.x=p[0].first;tmp.y=p[0].second;
    v[0][tmp.x][tmp.y]=1;
    q1.push(tmp);
    tmp.x=p[1].first;tmp.y=p[1].second;
    v[1][tmp.x][tmp.y]=1;
    q2.push(tmp);
    int timi=0;
    int flag=0;
    while(!flag){
        timi++;
        int cur1,cur2;
        cur1=q1.size();
        cur2=q2.size();
        if(cur1==0&&cur2==0){
            flag=-1;
            break;
        } 
        while(q1.size()&&cur1--){
            node now=q1.front();
            q1.pop();
            for(int i=0;i<8;i++){
                node tmp;
                tmp.x=now.x+dir[i][0];tmp.y=now.y+dir[i][1];
                if(v[1][tmp.x][tmp.y]){
                    flag=1;break;
                }
                if(check(tmp.x,tmp.y)&&!v[0][tmp.x][tmp.y]){
                    v[0][tmp.x][tmp.y]=1;
                    q1.push(tmp);
                }
            }
        }

        while(q2.size()&&cur2--){
            node now=q2.front();
            q2.pop();
            for(int i=0;i<4;i++){
                node tmp;
                tmp.x=now.x+dir[i][0];tmp.y=now.y+dir[i][1];
                if(v[0][tmp.x][tmp.y]){
                    flag=true;
                    break;
                }
                if(v[0][tmp.x][tmp.y]){
                    flag=1;break;
                }
                if(check(tmp.x,tmp.y)&&!v[1][tmp.x][tmp.y]){
                    v[1][tmp.x][tmp.y]=1;
                    q2.push(tmp);
                }
            }
        }
        if(flag==1)break;
        cur2=q2.size();
        while(q2.size()&&cur2--){
            node now=q2.front();
            q2.pop();
            for(int i=0;i<4;i++){
                node tmp;
                tmp.x=now.x+dir[i][0];tmp.y=now.y+dir[i][1];
                if(v[0][tmp.x][tmp.y]){
                    flag=true;
                    break;
                }
                if(check(tmp.x,tmp.y)&&!v[1][tmp.x][tmp.y]){
                    v[1][tmp.x][tmp.y]=1;
                    q2.push(tmp);
                }
            }
        }
    }
    if(flag==-1)cout<<"NO"<<endl;
    else {
        cout<<"YES"<<endl<<timi<<endl;
    }
    return 0;
}