uva 11045

自己試試看用stack來製造遞迴

我真的覺得自己像個腦殘，看來天賦點得不夠高。

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <string.h>
#include <limits.h>
#include <queue>
#include <stack>
using namespace std;
bool gra[31][37];//small adjacency matrix
int npeople,ncloth;
int mx[37];
int my[31];
int vy[37];

bool dfs(int x){

    stack<int> sx;
    stack<int> sy;
    bool flag=false;
    bool flag_2;
    bool vvy[ncloth];
    int y=0;
    do{
        if(flag){
            //退回上一步
            x=sx.top();
            sx.pop();
            sy.pop();
        }
        for(y=0;y<ncloth;y++){
            flag=true;
            if(gra[x][y] && !vy[y]){
                vy[y]=true;
                if(my[y]==-1){
                    mx[x]=y,my[y]=x;
                    //printf("x:%d y:%d\n",x,y);
                    while(!sx.empty()){
                        x=sx.top();
                        y=sy.top();
                        //printf("x:%d y:%d\n",x,y);
                        mx[x]=y,my[y]=x;
                        sx.pop(),sy.pop();
                    }
                    return true;
                }else{
                        sx.push(x);
                        sy.push(y);
                        x=my[y];
                        flag=false;
                        break;
                }
            }
        }
    }while(!sx.empty());
    return false;
    /*遞迴做法，跟演算法筆記一模一樣
    for (int y=0; y<ncloth; ++y)
        if (gra[x][y] && !vy[y])
        {
            vy[y] = true;
            // 找到擴充路徑
            if (my[y] == -1 || dfs(my[y]))
            {
                mx[x] = y; my[y] = x;
                return true;
            }
        }
    return false;*/
}

int main(){
    //[人數][衣服數]
    //一般的adjacency matrix並不是這樣建
    int n1,n2,n3,turn;
    int c1,c2;
    char s1[10],s2[10];
    scanf("%d",&n1);
    while(n1--){
        scanf("%d %d",&n2,&n3);
        npeople=n3,ncloth=n2;
        turn=n2/6;
        memset(gra,false,sizeof(gra));
        int ind=0;
        while(n3--){
            scanf("%s %s",s1,s2);
            if(s1[0]=='S'){
                c1=0;
            }else if(s1[0]=='X' && s1[1]=='S'){
                c1=1;
            }else if(s1[0]=='M'){
                c1=2;
            }else if(s1[0]=='L'){
                c1=3;
            }else if(s1[0]=='X' && s1[1]=='L'){
                c1=4;
            }else if(s1[0]=='X' && s1[1]=='X' && s1[2]=='L'){
                c1=5;
            }
            if(s2[0]=='S'){
                c2=0;
            }else if(s2[0]=='X' && s2[1]=='S'){
                c2=1;
            }else if(s2[0]=='M'){
                c2=2;
            }else if(s2[0]=='L'){
                c2=3;
            }else if(s2[0]=='X' && s2[1]=='L'){
                c2=4;
            }else if(s2[0]=='X' && s2[1]=='X' && s2[2]=='L'){
                c2=5;
            }
            for(int i=0;i<turn;i++,c1+=6,c2+=6){
                gra[ind][c1]=true;
                gra[ind][c2]=true;
            }
            ind++;
        }
        /*for(int i=0;i<npeople;i++){
            for(int j=0;j<ncloth;j++){
                if(gra[i][j]){
                    printf("1");
                }else{
                    printf("0");
                }
            }
            printf("\n");
        }*/
        //start max bipartite matching
        //
        memset(mx,-1,sizeof(mx));
        memset(my,-1,sizeof(my));
        int c=0;
        for(int x=0;x<npeople;x++){
            memset(vy,false,sizeof(vy));
            if(dfs(x)) c++;
            for(int i=0;i<ncloth;i++){
            //    printf("%d ",my[i]);
            }
            //printf("\n");
        }
        /*        printf("\n");
        printf("c:%d\n",c);*/
        if(c==npeople){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
    return 0;
}
/*
 *    S XS M L XL XXL
 *  0 1  2 3 4  5
 */