OJ Board

Code: Select all

#include <stdio.h>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <map>
#include <vector>
#include <queue>
#include <set>
using namespace std;

char domino[4][7][2]=
{
    {{0,3},{1,1},{3,4},{1,5},{0,2},{0,6},{4,6}},
    {{3,3},{4,4},{0,5},{2,4},{1,2},{3,6},{0,0}},
    {{1,3},{2,6},{6,6},{2,3},{1,6},{5,6},{4,5}},
    {{3,5},{2,2},{0,4},{5,5},{2,5},{0,1},{1,4}}
};

struct Node
{
    char link,opp;
    bool valid;
    Node(char link=-1,char opp=-1,bool valid=false)
    :link(link),opp(opp),valid(valid){}
    void print()  { cout << (int)link << (int)opp << (int)valid << " ";}
} adj[4][7][7];

char cnt[4][7];
char sum[4];
int win,loss,tie,prev;

void solve(char p,char u,char n,char l,char r)
{
    // Play current piece
    char v=adj[p][u][n].opp;
    char nn=adj[p][u][n].link;
    adj[p][u][n].valid=false;
    adj[p][v][nn].valid=false;
    sum[p]-=(u+v);
    
    // Game end check
    if(sum[p]==0 && (p!=1 || (p==1 && !adj[1][0][1].valid)))
    {
        if(p==0) win++;
        else loss++;
    }
    else
    {
        // Play Next piece
        bool played=false;
        for(char i=1;i<=4;i++)
        {
            played=false;
            char np=(p+i)%4;
            char j;
            // Play on left
            for(j=0;j<cnt[np][l];j++)
                if(adj[np][l][j].valid)
                {
                    solve(np,l,j,l,adj[np][l][j].opp);
                    played=true;
                }
            // Play on right
            for(j=0;j<cnt[np][r];j++)
                if(adj[np][r][j].valid)
                {
                    solve(np,r,j,adj[np][r][j].opp,r);
                    played=true;
                }
            // Exit if played piece.
            if(played) break;
        }
        
        // Not played -- Game ends here.
        if(!played)
        {
            if(sum[0]==sum[1] || sum[0]==sum[2] || sum[0]==sum[3]
               || sum[1]==sum[2] || sum[1]==sum[3] 
               || sum[2]==sum[3]) tie++;
            else
            {
                if(sum[0]<sum[1] && sum[0]<sum[2] && sum[0]<sum[3]) win++;
                else loss++;
            }
        }
    }
    
    // Unplay current piece
    adj[p][u][n].valid=true;
    adj[p][v][nn].valid=true;
    sum[p]+=(u+v);
    
    // Debug Output
    if(loss+win+tie>prev+1000000)
    {
        prev=loss+win+tie;
        cout << ".";
    }
    return;
}

int main()
{
    // Build Graph
    char p,i,j;
    for(p=0;p<4;p++)
        for(i=0;i<7;i++)
        {
            char u=domino[p][i][0], v=domino[p][i][1];
            adj[p][u][cnt[p][u]]=Node(cnt[p][v],v,true);
            adj[p][v][cnt[p][v]]=Node(cnt[p][u],u,true);
            cnt[p][u]++; if(v!=u) cnt[p][v]++;
            sum[p]+=u+v;
        }

    // Solve
    int u=0; int n=1; // nth block that has u.  This is (0,2).
    //cout << "Enter u and n (nth domino that has u, counting from left): ";
    //cin >> u >> n;
    int v=adj[0][u][n].opp;
    cout << "(u,v) is " << endl;
    cout << "(" << u << ":" << v << ")" << endl;
    solve(0,u,n,u,v);
    cout << endl << "Wins Losses Ties" << endl;
    cout << win << "," << loss << "," << tie << endl;
    system("pause");
    return 0;
}