题解 | #放苹果#

#include <iostream>
#include<queue>
#include<algorithm>
using namespace std;

struct state{
    int left;
    int plates[20];
};

bool ifnew(state *rec,state s,int cnt,int n){
    
    for(int i = 0;i < cnt;i++){
    	bool flag = false;
        for(int j = 0;j < n;j++){
            if(s.plates[j] != (rec+i)->plates[j]){
            	flag = true;
            	break;
			}   
        }
        if(!flag)
        	return false;
    }
    return true;
}

int main() {
    int m, n,cnt = 0,ways = 0;
    cin >> m >> n;
    state init;
    init.left = m;
    for(int i = 0;i < n;i++)
    	init.plates[i] = 0;
    	
    state record[500];
    queue<state> q;
    q.push(init);
    while (!q.empty()){
        for(int i = 0;i < n;i++){
            state s = q.front();
            s.left--;
            s.plates[i]++;
            sort(s.plates,s.plates+n);
            if(ifnew(record,s,cnt,n)){
            	
                record[cnt++] = s;
                if(s.left == 0){
                /*
            	cout << "(" << s.left << ",";
            	for(int i = 0;i < n;i++)
                	cout << s.plates[i] <<",";
            	cout << ")";
            	*/
            		 ways++;
				}
                   
                else
                    q.push(s);
            }
        }
        q.pop();

    }
    cout << ways;

}
// 64 位输出请用 printf("%lld")

广度优先搜索