4 条题解

  • 1
    @ 2025-3-26 17:05:46

    dfs解法:(相对于正常的vis访问数组,本题的vis要多一个维度,因为某一点点的访问情况跟方向有关,所以要加上4个方向)

    #include <iostream>
    using namespace std;
    const int N = 201;
    int m,n;
    char mp[N][N];
    bool vis[N][N][4];
    int dir[4][2] = {-1,0,1,0,0,1,0,-1};
    
    void dfs(int x,int y,int d)
    {
      int nx = x + dir[d][0];
      int ny = y + dir[d][1];
      if(mp[nx][ny] == '.' && !vis[nx][ny][d])
      {
        vis[nx][ny][d] = true;
        dfs(nx,ny,d);
      }
      if(mp[nx][ny] == '#')
      {
        for(int i = 0;i<4;i++)
        {
          nx = x + dir[i][0];
          ny = y + dir[i][1];
          if(mp[nx][ny] == '.' && !vis[nx][ny][i])
          {
            vis[nx][ny][i] = true;
            dfs(nx,ny,i);
          }
        }
      }
    }
    
    int main()
    {
      cin>>n>>m;
      for(int i = 0;i<n;i++)
      {
        for(int j = 0;j<m;j++)
          cin>>mp[i][j];
      }
      if(mp[2][1] == '.')
      {
        vis[1][1][1] = true;
        dfs(1,1,1);
      }
      if(mp[1][2] == '.') 
      {
        vis[1][1][2] = true;
        dfs(1,1,2);
      }
      int ans = 1;
      for(int i = 1;i<n-1;i++)
      {
        for(int j = 1;j<m-1;j++)
        {
          for(int k = 0;k<4;k++)
          {
            if(i == 1 && j == 1) continue;
            if(mp[i][j] == '.' && vis[i][j][k])
            {
              ans++;
              break;
            }
          }
        }
      }
      cout<<ans;
      return 0;
    }
    

    信息

    ID
    297
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    44
    已通过
    18
    上传者