杂题训练 2020.7.8

···水题AC场···
好奇怪的游戏
https://www.luogu.com.cn/problem/P1747

#include <bits/stdc++.h>
using namespace std;
const int N=30;
int d[N][N];
bool v[N][N];
int dx[12]={1,2,2,1,-1,-2,-2,-1,2,2,-2,-2};
int dy[12]={2,1,-1,-2,-2,-1,1,2,2,-2,-2,2};
int main()
{
    int x1,y1;
    cin>>x1>>y1;
    queue<pair<int,int> >q;
    q.push(make_pair(x1,y1));
    while(q.size()){
        pair<int,int>now=q.front();
      //  cout<<now.first<<" "<<now.second<<endl;
        q.pop();
        for(int k=0;k<12;k++){
            int nx=now.first+dx[k];
            int ny=now.second+dy[k];
            if(nx>=1&&nx<=20&&ny>=1&&ny<=20&&!v[nx][ny]){
                v[nx][ny]=1;
                d[nx][ny]=d[now.first][now.second]+1;
                q.push(make_pair(nx,ny));
            }
        }
    }
    cout<<d[1][1]<<endl;
    memset(d,0,sizeof(d));
    memset(v,0,sizeof(v));
    int x2,y2;
    cin>>x2>>y2;
    q.push(make_pair(x2,y2));
    while(q.size()){
        pair<int,int>now=q.front();
        q.pop();
        for(int k=0;k<12;k++){
            int nx=now.first+dx[k];
            int ny=now.second+dy[k];
            if(nx>=1&&nx<=20&&ny>=1&&ny<=20&&!v[nx][ny]){
                v[nx][ny]=1;
                d[nx][ny]=d[now.first][now.second]+1;
                q.push(make_pair(nx,ny));
            }
        }
    }
    cout<<d[1][1];
    return 0;
}

离开中山路
https://www.luogu.com.cn/problem/P1746

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
int d[N][N];
bool v[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    queue<pair<int,int> >q;
    q.push(make_pair(x1,y1));
    v[x1][y1]=1;
    while(q.size()){
        pair<int,int>now=q.front();
      //  cout<<now.first<<" "<<now.second<<endl;
        q.pop();
        v[now.first][now.second]=1;
        for(int k=0;k<4;k++){
            int nx=now.first+dx[k];
            int ny=now.second+dy[k];
            if(nx==x2&&ny==y2){
                d[nx][ny]=d[now.first][now.second]+1;
                cout<<d[x2][y2]<<endl;
                return 0;
            }
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!v[nx][ny]&&g[nx][ny]!='1'){
                v[nx][ny]=1;
                d[nx][ny]=d[now.first][now.second]+1;
                q.push(make_pair(nx,ny));
            }
        }
    }
    cout<<"-1"<<endl;
    return 0;
}

Mzc和男家丁的游戏
https://www.luogu.com.cn/problem/P2298

#include <bits/stdc++.h>
using namespace std;
const int N=2010;
char g[N][N];
int d[N][N];
bool v[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int main()
{
    int n,m,sx,sy,gx,gy;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
            if(g[i][j]=='m'){
                sx=i;
                sy=j;
            }
            else if(g[i][j]=='d'){
                gx=i;
                gy=j;
            }
        }
    }
    queue<pair<int,int> >q;
    q.push(make_pair(sx,sy));
    v[sx][sy]=1;
    while(q.size()){
        pair<int,int>now=q.front();
      //  cout<<now.first<<" "<<now.second<<endl;
        q.pop();
        v[now.first][now.second]=1;
        for(int k=0;k<4;k++){
            int nx=now.first+dx[k];
            int ny=now.second+dy[k];
            if(nx==gx&&ny==gy){
                d[nx][ny]=d[now.first][now.second]+1;
                cout<<d[gx][gy]<<endl;
                return 0;
            }
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!v[nx][ny]&&g[nx][ny]!='#'){
                v[nx][ny]=1;
                d[nx][ny]=d[now.first][now.second]+1;
                q.push(make_pair(nx,ny));
            }
        }
    }
    cout<<"No Way!"<<endl;
    return 0;
}

血色先锋队
https://www.luogu.com.cn/problem/P1332

#include <bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,a,b;
int d[N][N];
bool v[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int main()
{
    queue<pair<int,int> >q;
    cin>>n>>m>>a>>b;
    for(int i=1;i<=a;i++){
        int x,y;
        cin>>x>>y;
        q.push(make_pair(x,y));
        v[x][y]=1;
    }
    pair<int,int> bp[b+1];
    for(int i=1;i<=b;i++)
        cin>>bp[i].first>>bp[i].second;
    while(q.size()){
        pair<int,int> now=q.front();q.pop();
        for(int k=0;k<4;k++){
            int nx=now.first+dx[k];
            int ny=now.second+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!v[nx][ny]){
                d[nx][ny]=d[now.first][now.second]+1;
                q.push(make_pair(nx,ny));
                v[nx][ny]=1;
            }
        }
    }
    for(int i=1;i<=b;i++)
        cout<<d[bp[i].first][bp[i].second]<<endl;
    return 0;
}

求细胞数量
https://www.luogu.com.cn/problem/P1451

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,res;
char g[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
void bfs(int x,int y){
    g[x][y]='0';
    queue<pair<int,int> >q;
    q.push(make_pair(x,y));
    while(q.size()){
        pair<int,int>now=q.front();q.pop();
        for(int k=0;k<4;k++){
            int nx=now.first+dx[k];
            int ny=now.second+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&g[nx][ny]!='0'){
                g[nx][ny]='0';
                q.push(make_pair(nx,ny));
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]>='1'&&g[i][j]<='9'){
                bfs(i,j);
                res++;
            }
        }
    }
    cout<<res;
    return 0;
}

[USACO19JAN]Icy Perimeter S
https://www.luogu.com.cn/problem/P5198

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
bool v[N][N];
int anss=1,ansc,n;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
void bfs(int i,int j){
    int nows=1,nowc=0;
    for(int k=0;k<4;k++){
        int nx=i+dx[k];
        int ny=j+dy[k];
        if(g[nx][ny]=='.') nowc++;
    }
    queue<pair<int,int> >q;
    q.push(make_pair(i,j));
    v[i][j]=1;
    while(q.size()){
        pair<int,int> now=q.front();q.pop();
        for(int k=0;k<4;k++){
            int nx=now.first+dx[k];
            int ny=now.second+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!v[nx][ny]&&g[nx][ny]=='#'){
                v[nx][ny]=1;
                nows++;
                for(int t=0;t<4;t++){
                    int nnx=nx+dx[t];
                    int nny=ny+dy[t];
                    if(g[nnx][nny]=='.') nowc++;
                }
                q.push(make_pair(nx,ny));
            }
        }
    }
    if(nows>=anss){
        anss=nows;
        ansc=nowc;
    }
    else if(nows==anss){
        ansc=max(ansc,nowc);
    }
}
void work(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!v[i][j]&&g[i][j]=='#') bfs(i,j);
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=n+1;j++)
            g[i][j]='.';
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
    /*for(int i=0;i<=n+1;i++){
        for(int j=0;j<=n+1;j++){
            cout<<g[i][j];
        }
        cout<<endl;
    }*/
    work();
    cout<<anss<<" "<<ansc;
    return 0;
}