3 条题解

  • 2
    @ 2023-1-6 11:58:12
    #include<iostream>
    #include<string.h>
    #include<queue>
    using namespace std;
    struct id
    {
    	int x,y,s;
    };
    queue<id>q;
    int n,m,x,y,sx,sy,ans,k;
    int xx[8]={-1,-1,-1,0,0,1,1,1};
    int yy[8]={-1,0,1,-1,1,-1,0,1};
    bool qp[110][110];
    char ch;
    int main()
    {
    	memset(qp,false,sizeof(qp));
    	cin>>m>>n>>x>>y;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			cin>>ch;
    			if(ch=='.')qp[i][j]=true;
    		}
    	}
    	sy=x;
    	sx=n-y+1;
    	q.push(id{sx,sy,0});
    	qp[sx][sy]=false;
    	while(!q.empty())
    	{
    		int tx=q.front().x;
    		int ty=q.front().y;
    		ans=q.front().s;
    		q.pop();
    		for(int i=0;i<8;i++)
    		{
    			int nx=tx+xx[i];
    			int ny=ty+yy[i];
    			if(qp[nx][ny])
    			{
    				q.push(id{nx,ny,ans+1});
    				qp[nx][ny]=false;
    			}
    		}
    	}
    	cout<<ans;
    	return 0;
    }
    
    • 1
      @ 2026-10-11 15:41:40
      #include<bits/stdc++.h>
      using namespace std;
      #define int long long
      const int N=105;
      int n,m;
      int a[N][N],dis[N][N];
      int dx[]={-1,-1,-1,0,0,1,1,1};
      int dy[]={-1,0,1,-1,1,-1,0,1};
      queue<pair<int,int> > que;
      bool inside(int nx,int ny){
          return nx>=1&&nx<=n&&ny>=1&&ny<=m;
      }
      void bfs(int sr,int sc){
          memset(dis,0x3f,sizeof(dis));
          dis[sr][sc]=0;
          que.push({sr,sc});
          while(!que.empty()){
              int x=que.front().first;
              int y=que.front().second;
              que.pop();
              for(int i=0;i<8;i++){
                  int nx=x+dx[i];
                  int ny=y+dy[i];
                  if(!inside(nx,ny)){
      			    continue;
      			}
                  if(a[nx][ny]=='*'){
      			    continue;
      			}
                  if(dis[x][y]+1<dis[nx][ny]){
                      dis[nx][ny]=dis[x][y]+1;
                      que.push({nx,ny});
                  }
              }
          }
      }
      signed main(){
          ios::sync_with_stdio(false);
          cin.tie(0);
          cout.tie(0);
          int Y,X,Mx,My;
          cin>>Y>>X>>Mx>>My;
          n=X;
      	m=Y;
          int sr=X-My+1;
          int sc=Mx;
          for(int i=1;i<=X;i++){
              string s;
              cin>>s;
              for(int j=1;j<=Y;j++){
                  a[i][j]=s[j-1];
              }
          }
          bfs(sr,sc);
          int ret=0;
          for(int i=1;i<=n;i++){
              for(int j=1;j<=m;j++){
                  if(a[i][j]=='.'){
                      ret=max(ret, dis[i][j]);
                  }
              }
          }
          cout<<ret<<endl;
          return 0;
      }
      //包AC的
      
      • 1
        @ 2023-5-13 12:48:48
        #include<iostream>
        #include<string.h>
        #include<queue>
        using namespace std;
        struct id
        {
        int x,y,s;
        };
        queue<id>q;
        int n,m,x,y,sx,sy,ans,k;
        int xx[8]={-1,-1,-1,0,0,1,1,1};
        int yy[8]={-1,0,1,-1,1,-1,0,1};
        bool qp[110][110];
        char ch;
        int main()
        {
        memset(qp,false,sizeof(qp));
        cin>>m>>n>>x>>y;
        for(int i=1;i<=n;i++)
        {
        for(int j=1;j<=m;j++)
        {
        cin>>ch;
        if(ch=='.')qp[i][j]=true;
        }
        }
        sy=x;
        sx=n-y+1;
        q.push(id{sx,sy,0});
        qp[sx][sy]=false;
        while(!q.empty())
        {
        int tx=q.front().x;
        int ty=q.front().y;
        ans=q.front().s;
        q.pop();
        for(int i=0;i<8;i++)
        {
        int nx=tx+xx[i];
        int ny=ty+yy[i];
        if(qp[nx][ny])
        {
        q.push(id{nx,ny,ans+1});
        qp[nx][ny]=false;
        }
        }
        }
        cout<<ans;
        return 0;
        }
        
        • 1

        信息

        ID
        2816
        时间
        1000ms
        内存
        256MiB
        难度
        7
        标签
        递交数
        121
        已通过
        25
        上传者