Contain Virus O(n*m*max(n,m)) || DFS || Leetcode Hard
Intuition\n Describe your first thoughts on how to solve this problem. \nBasically I am trying to traverse First ifected cell then dfs after that spreading the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBasically I am trying to traverse First ifected cell then dfs after that spreading the infected case by adjacent untill I get the optimal answer,So that\'s why while(true) every time I chck that infected cell then dfs and it will repaeting\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBasically using through DFS when the infected cell is found then it will return wall number it will comparison through the set. after that when one traversal iscompleted and it addded 1 as adjacent after checking that will not violate the rules of matrix overflow\n\n# Complexity\n- Time complexity: O(n*m*max(m,n))\nn =isinfectedd.size()\nm = isinfectedd[0].size()\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(n*m)\nwhere \nn =isinfectedd.size()\nm = isinfectedd[0].size()\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\npublic:\n    int n,m,r,mx;\n    int col;\n    int ans;\n    unordered_set<int> st;\n    int wall;\n    vector<vector<int>> isInfected;\n\n    int dfs(int i,int j)\n    {\n        if(i<0 || j<0 || i>=n || j>=m || isInfected[i][j]!=1)\n        {\n            return 0;\n        }\n\n        int ans  = 0;\n\n        if(i-1>=0 && isInfected[i-1][j] == 0)\n        {\n            st.insert((i-1)*m + j);\n            ans++;\n        }\n        if(i+1<n && isInfected[i+1][j] == 0)\n        {\n            st.insert((i+1)*m + j);\n            ans++;\n        }\n\n        if(j-1>=0 && isInfected[i][j-1] == 0)\n        {\n            st.insert(i*m + (j-1));\n            ans++;\n        }\n\n        if(j+1<m && isInfected[i][j+1] == 0)\n        {\n            st.insert(i*m + (j+1));\n            ans++;\n        }\n\n\n        isInfected[i][j] = col;\n\n        ans+=dfs(i+1,j);\n        ans+=dfs(i-1,j);\n        ans+=dfs(i,j-1);\n        ans+=dfs(i,j+1);\n\n\n        return ans;\n\n\n    }\n    int containVirus(vector<vector<int>>& isInfectedd) {\n\n\n        n = isInfectedd.size();\n        m = isInfectedd[0].size();\n\n        isInfected = isInfectedd;\n        ans = 0;\n\n       \n        while(true)\n        {\n             mx = 0;\n             col = 2;\n            for(int i=0;i<n;i++)\n            {\n                for(int j=0;j<m;j++)\n                {\n                    if(isInfected[i][j] == 1)\n                    {\n                        st.clear();\n                        int w = dfs(i,j);\n                        if(mx<st.size())\n                        {\n                            mx = st.size();\n                            wall = w;\n                            r = col;\n                        }\n                        col++;\n                    }\n        \n                }\n            }\n\n            if(mx == 0)\n            {\n                break;\n            }\n            ans+=wall;\n\n\n            for(int i=0;i<n;i++)\n            {\n                for(int j=0;j<m;j++)\n                {\n                    if(isInfected[i][j] == r)\n                    {\n                        isInfected[i][j] = 1e9;\n                    }\n                    else if(isInfected[i][j] > 1 and isInfected[i][j] != 1e9)\n                    {\n                        isInfected[i][j] = 1;\n                        if(i-1>=0 and !isInfected[i-1][j])\n                        {\n                            isInfected[i-1][j] = 1;\n                        }\n                         if(i+1<n and !isInfected[i+1][j])\n                        {\n                            isInfected[i+1][j] = 1;\n                        }\n                         if(j-1>=0 and !isInfected[i][j-1])\n                        {\n                            isInfected[i][j-1] = 1;\n                        }\n                         if(j+1<m and !isInfected[i][j+1])\n                        {\n                            isInfected[i][j+1] = 1;\n                        }\n                    }\n                }\n            }\n        }\n\n\n        return ans;\n\n        \n    }\n};\n```
['Graph', 'Matrix', 'C++']