ACM第二次排名赛

D   巧克力

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N=1000;

int ma=-1,ans=0;
int dx[10]={-1,0,1,0};
int dy[10]={0,1,0,-1};
typedef pair<int,int> PII;
string g[N];

int n,m;
bool st[N][N];

void bfs(int a,int b)
{
    int num=1;
    queue<PII> q;
    q.push({a,b});
    st[a][b]=true;

    while(q.size())
    {
        auto t=q.front();
        q.pop();

        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i];
            int y=t.second+dy[i];

            if(x>=0 && x<n && y>=0 && y<m && !st[x][y] &&g[x][y]!='1' )
            {
                st[x][y]=true;
                q.push({x,y});
                num++;
            }
        }
    }
    ma=max(ma,num);
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>g[i];
    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='0'&&!st[i][j])//没被标记
            {
                bfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans<<" "<<ma;
    return 0;
}

E   寻找豆汁 ( Easy )

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

const int N=1000;
typedef pair<int,int> PII;
int n,m;
bool st[N][N];
string g[N];
int a,b,c,d;
int dx[10] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[10] = {-1, 0, 1, 1, 1, 0, -1, -1};

void bfs()
{
    queue<PII> q;
    q.push({a,b});
    st[a][b]=true;

    while(!q.empty())
    {
        auto t=q.front();
        q.pop();

        for(int i=0;i<8;i++)
        {
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(x> 0 && x<=n && y> 0 &&y<=m && g[x][y]=='.' && !st[x][y])
            {
                if(x==c && y==d)
                {
                    cout<<"YES";
                    return;
                }
                st[x][y]=true;
                q.push({x,y});
            }
        }
    }
    cout<<"NO";
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>g[i];
        g[i]=" "+g[i];
    }
    cin>>a>>b>>c>>d;

    bfs();
    return 0;
}

F   寻找豆汁 ( Hard )

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N=1000;

typedef pair<int,int> PII;
int dx[10]={-1,-1,0,1,1,1,0,-1};
int n,m,k,x,y;
int dy[10]={0,1,1,1,0,-1,-1,-1};

string g[N];
bool st[N][N];
int a,b,c,d;
map<PII,PII> mp;

void bfs()
{
    queue<PII> q;
    q.push({a,b});
    st[a][b]=true;
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        if(mp[{t.first,t.second}].first!=0)
        {
            x=mp[{t.first,t.second}].first;
            y=mp[{t.first,t.second}].second;
        
            if(x>0 && x<=n && y>0 && y<=m && !st[x][y] && g[x][y]=='.')
            {
                if(x==c&&y==d)
                {
                    cout<<"Yes";
                    return;
                }
                st[x][y]=true;
                q.push({x,y});
            }
        }
        for(int i=0;i<8;i++)
        {
            x=t.first+dx[i];
            y=t.second+dy[i];
            if(x>0&&x<=n&&y>0&&y<=m&&!st[x][y]&&g[x][y]=='.')
            {
                if(x==c&&y==d)
                {
                    cout<<"Yes";
                    return;
                }
                st[x][y]=true;
                q.push({x,y});
            }
        }
    }
    cout<<"NO";
}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>g[i];
        g[i]=" "+g[i];
    }
    while(k--)
    {
        cin>>a>>b>>c>>d;
        mp[{a,b}]={c,d};
    }
    cin>>a>>b>>c>>d;
    bfs();
    return 0;
}

G   路障

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N=1000;

int st[N][N];
struct op
{
    int first,second,t;
};

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool ch[N][N];
int x,y;
int n,a,b;

void bfs()
{
    queue<op>q;
    q.push({1,1,0});
    ch[1][1]=true;
    while(q.size())
    {
        auto r=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            x=r.first+dx[i];
            y=r.second+dy[i];
            if(x>0 && x<=n && y>0 && y<=n && ch[x][y]==false && r.t+1<=st[x][y])
            {
                if(x==n&&y==n)
                {
                    cout<<"Yes"<<endl;
                    return;
                }
                ch[x][y]=true;
                q.push({x,y,r.t+1});
            }
        }
    }
    cout<<"No"<<endl;

}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(st,0x3f3f3f3f,sizeof st);
        memset(ch,false,sizeof ch);
        cin>>n;
        for(int i=1;i<=n*2-2;i++)
        {
            cin>>a>>b;
            st[a][b]=i;
        }

        bfs();
    }
    return 0;
}