打扫房间-yiteyi-C++库

给定一个带有“*”和“.”的正方形网格的房间分别代表不整洁和正常的细胞。你需要弄清楚房间是否可以打扫。有一台机器可以帮你完成这项任务，但它只能清洗正常细胞。不整洁的单元格不能用机器清洗，除非您已经清洗了其行或列中的正常单元格。现在，看看房间能不能打扫一下。

null

输入如下： 第一行包含 $n$ 房间的大小。接下来的n行包含对行[i][j]所在的每一行的描述 $*$ “如果它比其他地方更不整洁的话” $.$ “如果是正常细胞。

例如：

Input : 3
        .**
        .**
        .**
Output :Yes, the room can be cleaned.
        1 1
        2 1
        3 1
Input :4
       ****
       ..*.
       ..*.
       ..*.
Output : house cannot be cleaned.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法： 最小单元格数可以是n。这是唯一可能的答案，因为它需要一个’ $.$ “在每一行和每一列中。如果特定列和给定行包含’ $*$ “在所有的牢房里，人们都知道房子不能打扫。遍历每一行，找到 $.$ “这可以用于机器。使用此步骤两次，检查每一行的每一列，然后检查每一列的每一行。然后检查两个答案中是否有一个是n。如果是，那么房子可以打扫，否则不行。这种方法将为我们提供所需的最低答案。

在第一个示例中，机器将清洁单元（1,1）、（2,1）、（3,1），以清洁整个房间。在第二个例子中 $1^{st}$ 争吵已经结束了 $*$ “还有里面的每个细胞。” $3^{rd}$ 列包含’ $*$ 所以房子不能打扫。 $1^{st}$ 行不能以任何方式清洁。

C++

                         // CPP code to find whether                       
                         // house can be cleaned or not                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // Matrix A stores the string                       
                         char                                     A[105][105];                       
                                   
                         // ans stores the pair of indices                       
                         // to be cleaned by the machine                       
                         vector<pair<                                     int                                     ,                                     int                                     > > ans;                       
                                   
                         // Function for printing the                       
                         // vector of pair                       
                         void                                     print()                       
                         {                       
                                                 cout <<                                     "Yes, the house can be"                       
                                                 <<                                     " cleaned."                                     << endl;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < ans.size(); i++)                       
                                                 cout << ans[i].first <<                                     " "                       
                                                 << ans[i].second << endl;                       
                         }                       
                                   
                         // Function performing calculations                       
                         int                                     solve(                                     int                                     n)                       
                         {                       
                                                 // push every first cell in                       
                                                 // each row containing '.'                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 for                                     (                                     int                                     j = 0; j < n; j++) {                       
                                                 if                                     (A[i][j] ==                                     '.'                                     ) {                       
                                                 ans.push_back(make_pair(i + 1, j + 1));                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // If total number of cells are                       
                                                 // n then house can be cleaned                       
                                                 if                                     (ans.size() == n) {                       
                                                 print();                       
                                                 return                                     0;                       
                                                 }                       
                                   
                                                 ans.clear();                       
                                   
                                                 // push every first cell in                       
                                                 // each column containing '.'                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 for                                     (                                     int                                     j = 0; j < n; j++) {                       
                                                 if                                     (A[j][i] ==                                     '.'                                     ) {                       
                                                 ans.push_back(make_pair(i + 1, j + 1));                       
                                                 break                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // If total number of cells are                       
                                                 // n then house can be cleaned                       
                                                 if                                     (ans.size() == n) {                       
                                                 print();                       
                                                 return                                     0;                       
                                                 }                       
                                                 cout <<                                     "house cannot be cleaned."                       
                                                 << endl;                       
                         }                       
                                   
                         // Driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 3;                       
                                                 string s =                                     ""                                     ;                       
                                                 s +=                                     ".**"                                     ;                       
                                                 s +=                                     ".**"                                     ;                       
                                                 s +=                                     ".**"                                     ;                       
                                                 int                                     k = 0;                       
                                   
                                                 // Loop to insert letters from                       
                                                 // string to array                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 for                                     (                                     int                                     j = 0; j < n; j++)                       
                                                 A[i][j] = s[k++];                       
                                                 }                       
                                                 solve(n);                       
                                                 return                                     0;                       
                         }                       

Python3

                         # Python3 code to find whether                       
                         # house can be cleaned or not                       
                                   
                         # Matrix A stores the string                       
                         A                                     =                                     [[                                     0                                     for                                     i                                     in                                     range                                     (                                     105                                     )]                                     for                                     j                                     in                                     range                                     (                                     105                                     )]                       
                                   
                         # ans stores the pair of indices                       
                         # to be cleaned by the machine                       
                         ans                                     =                                     []                       
                                   
                         # Function for printing the                       
                         # vector of pair                       
                         def                                     printt():                       
                                   
                                                 print                                     (                                     "Yes, the house can be cleaned."                                     )                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (ans)):                       
                                                 print                                     (ans[i][                                     0                                     ], ans[i][                                     1                                     ])                       
                                   
                         # Function performing calculations                       
                         def                                     solve(n):                       
                                                 global                                     ans                       
                                   
                                                 # push every first cell in                       
                                                 # each row containing '.'                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 for                                     j                                     in                                     range                                     (n):                       
                                                 if                                     (A[i][j]                                     =                                     =                                     '.'                                     ):                       
                                                 ans.append([i                                     +                                     1                                     , j                                     +                                     1                                     ])                       
                                                 break                       
                                   
                                                 # If total number of cells are                       
                                                 # n then house can be cleaned                       
                                                 if                                     (                                     len                                     (ans)                                     =                                     =                                     n):                       
                                                 printt()                       
                                                 return                                     0                       
                                   
                                                 ans                                     =                                     []                       
                                   
                                                 # push every first cell in                       
                                                 # each column containing '.'                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 for                                     j                                     in                                     range                                     (n):                       
                                                 if                                     (A[j][i]                                     =                                     =                                     '.'                                     ):                       
                                                 ans.append([i                                     +                                     1                                     , j                                     +                                     1                                     ])                       
                                                 break                       
                                   
                                                 # If total number of cells are                       
                                                 # n then house can be cleaned                       
                                                 if                                     (                                     len                                     (ans)                                     =                                     =                                     n):                       
                                                 printt()                       
                                                 return                                     0                       
                                                 print                                     (                                     "house cannot be cleaned."                                     )                       
                                   
                         # Driver function                       
                         n                                     =                                     3                       
                         s                                     =                                     ""                       
                         s                                     +                                     =                                     ".**"                       
                         s                                     +                                     =                                     ".**"                       
                         s                                     +                                     =                                     ".**"                       
                         k                                     =                                     0                       
                                   
                         # Loop to insert letters from                       
                         # string to array                       
                         for                                     i                                     in                                     range                                     (n):                       
                                                 for                                     j                                     in                                     range                                     (n):                       
                                                 A[i][j]                                     =                                     s[k]                       
                                                 k                                     +                                     =                                     1                       
                                   
                         solve(n)                       
                                   
                         # This code is contributed by shubhamsingh10                       

输出：

Yes, the house can be cleaned.
1 1
2 1
3 1

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章