For some reason, I can not get the same answer as you and LayCurse.
Do you care to share your WA code, so we can compare and see if there are different
btw, I assume you cannot pass if you have a piece that you can play, and after no one can play the game ends.
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;
}