graph problem — counting rooms

Revision en1, by moghit_ad, 2021-11-11 00:29:28

hi everyone this is my first time trying to solve a graph problem after learning a DFS algorithm i tried to solve this one on cses but it giving WA on some test cases can anyone tell me where's prob on my code ? here's my code: bool vis[1001][1001]; char arr[1001][1001]; int n,m; bool valid(int x,int y){ if(x>n or x<1 or y<1 or y>m)return false; else if (vis[x][y]==true or arr[x][y]=='#')return false; else return true; } void dfs(int x,int y){ vis[x][y]=true; if(valid(x-1,y))dfs(x-1, y); else if (valid(x,y+1))dfs(x , y+1); else if(valid(x,y-1))dfs(x , y-1); else if(valid(x+1,y))dfs(x+1, y);

} void solve(){ memset(vis,false,sizeof(vis)); cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++)cin>>arr[i][j]; } int cnt=0; for(int i =1;i<=n;i++){ for(int j=1;j<=m;j++){ if(arr[i][j]=='.' and vis[i][j]==false){ cnt++; dfs(i,j); } } } cout<<cnt;

}

Tags dfs, bfs, graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English moghit_ad 2021-11-11 02:09:37 866
en2 English moghit_ad 2021-11-11 02:07:24 22
en1 English moghit_ad 2021-11-11 00:29:28 1151 Initial revision (published)