lll

lyxqqq1 · 2024-12-14 16:05:09 · 个人记录

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N{
    int x,y;
};
int qx,qy,vis[1005][1005],n,a[1005][1005];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ck(int x,int y)
{
    if(x<0||x>n+1||y<0||y>n+1)
        return 1;
    if(vis[x][y]||a[x][y])
        return 1;
    return 0;   
}
int bfs()
{
    queue<N>q;
    vis[qx][qy]=1;
    q.push({qx,qy});
    while(q.size())
    {
        N t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(ck(nx,ny))
                continue;
            q.push({nx,ny});
            vis[nx][ny]=1;
        }
    }
    return -1;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    bfs();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]!=1 and vis[i][j]==0)
                cout<<"2 ";
            else
                cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
} 

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct N{
    int x,y;
};
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int sum[1000005];
char a[1005][1005];
int l,vis[1005][1005],b[1005][1005];
int ck(int x,int y,int x1,int y1)
{
    if(x<1||x>n||y<1||y>n)
        return 1;
    if(vis[x][y]||a[x][y]==a[x1][y1])
        return 1;
    return 0;
}
int qx,qy;
int bfs()
{
    queue<N>q;
    b[qx][qy]=l;
    q.push({qx,qy});
    vis[qx][qy]=1;
    while(q.size())
    {
        N t=q.front();
        q.pop();
        sum[l]++;
        for(int i=0;i<4;i++)
        {
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(ck(nx,ny,t.x,t.y))
                continue;
            vis[nx][ny]=1;
            b[nx][ny]=l;
            q.push({nx,ny});
        }
    }
    return -1;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!vis[i][j])
            {
                qx=i,qy=j,l=l+1;
                bfs();
            }
        }
    }
    while(m--)
    {
        cin>>qx>>qy;
        cout<<sum[b[qx][qy]]<<endl;
    }
    return 0;
}

#include<bits/stdc++.h> 
#define int long long
using namespace std;
int qx,t,qy,n,m,vis[1005][1005];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char a[1005][1005];
int num[1005][1005];
struct N{
    int x,y,p,v;
};
int ck(int x,int y)
{
    if(x<1||x>n||y<1||y>n)
        return 1;
    if(a[x][y]=='#')
        return 1;
    return 0;
}
int bfs(){
    queue<N>q;
    q.push({qx,qy,0,0});
    vis[qx][qy]=1;
    while(q.size())
    {
        N t=q.front();
        q.pop();
        if(a[t.x][t.y]=='O')
            return t.p;
        for(int i=0;i<4;i++)
        {
            int nx=t.x+dx[i],ny=dy[i]+t.y;

            if(ck(nx,ny))
            {
                continue;
            }
            if(a[nx][ny]=='X' and t.v==0)
            {
                continue;
            }
            int vi=t.v-1;
            if(vi<0)
                vi=0;
            if(a[nx][ny]=='%')
            {
                vi=m;
            }
            if(vi<=num[nx][ny]&&vis[nx][ny])
                continue;
            num[nx][ny]=vi;
            vis[nx][ny]=1;
            q.push({nx,ny,t.p+1,vi});
        }
    }
    return -1;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    a[n][n]='O';
    qx=1,qy=1;
    cout<<bfs()<<endl;  return 0;
}