atcoder ABC 358-C题详解

Problem Statement

In AtCoder Land, there are N popcorn stands numbered 1 to N. They have M different flavors of popcorn, labeled 1,2,…,M, but not every stand sells all flavors of popcorn.

Takahashi has obtained information about which flavors of popcorn are sold at each stand. This information is represented by N strings S1,S2,…,SN of length M. If the j-th character of Si is o, it means that stand i sells flavor j of popcorn. If it is x, it means that stand i does not sell flavor j. Each stand sells at least one flavor of popcorn, and each flavor of popcorn is sold at least at one stand.

Takahashi wants to try all the flavors of popcorn but does not want to move around too much. Determine the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Constraints

N and M are integers.
1≤N,M≤10
Each Si is a string of length M consisting of o and x.
For every i (1≤i≤N), there is at least one o in Si.
For every j (1≤j≤M), there is at least one i such that the j-th character of Si is o.

Input

The input is given from Standard Input in the following format:

N M
S1
S2
⋮
SN

Output

Print the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Sample Input 1

3 5
oooxx
xooox
xxooo

Sample Output 1

2
By visiting the 1st and 3rd stands, you can buy all the flavors of popcorn. It is impossible to buy all the flavors from a single stand, so the answer is 2.

Sample Input 2

3 2
oo
ox
xo

Sample Output 2

Sample Input 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

Sample Output 3

思路分析：

可以使用二进制，本题组合数为2的2次方，为加快速度可以用左移运算，基本思路已经在代码中注释出来了。

code：

#include <iostream>
#include <vector>
#include <bitset>
#include <string>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;//n小摊数量m爆米花口味的数量
    vector<string>s(n);//等价于char s[i][j];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    vector<bitset<10>> b(n);//等价于bool b[12][10]；bitset<10>是一个10位的bitset
    //bitset初始化的时候所有的值默认全是0
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='o') b[i][j]=1;
        }
    }
    int ans=n;
    for(int x=0;x<(1<<n);x++){//实现了对小摊所有组合的枚举
        //x用于枚举所有可能的组合
        //1<<n是将1左移动n位。数值上等于2的n次方
        //比如n=1，1的二进制是0001，将1左移一位就是0010是2
        //n=2，1的二进制是0001，将1左移二位就是0100是4
        //n=3，1的二进制是0001，将1左移三位就是1000是8
        bitset<10> bx(x);//等价于 当x=2时，bx[0]=0,bx[1]=1,bx[2]=0,bx[3]=0,bx[4]=0,bx[5]=0……
        //小摊的组合情况
        bitset<10> sb;//记录有没有每个味道都出现(等价于初始化了一个bool)
        for(int i=0;i<n;i++){//遍历每个小摊
            if(bx[i])//如果第i个小摊在当前枚举的组合x种
                sb=sb | b[i];//(等价于sb｜=b[i];)那么我们直接把小摊b种所有的口味算进
        }
        if(sb.count()==m)
            ans=min(ans,(int)bx.count());
    }
    cout<<ans<<'\n';
    return 0;
}