返回题解分享
讨论 / 题解分享/ 帖子详情

迷宫 - 题解

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;
}
0 回复 0 转发 1 喜欢 5 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!