4 条题解
-
1
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
- 上传者