810 - A Dicey Problem

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
emka
New poster
Posts: 10
Joined: Sat Oct 19, 2002 7:20 am
Location: Singapore
Contact:

810 - A Dicey Problem

Post by emka »

Hi All,

I wrote the following code, and was working correctly on the sample testcases. Could anyone of you find where the bug is? OR maybe a testcase that will fail this program.

Thanks :)

[cpp]
#include <iostream>
#include <string>

using namespace std;

#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4

typedef struct{
int front, top;
} tdicepos;

typedef struct{
int row, col;
tdicepos pos;
} tcellinfo;

// ******** variable declaration ********
tcellinfo stack[600];
int stackcnt, cnt;
int r,c,posx,posy;
int board[10][10];
bool foundpath;
// -------- variable declaration --------

tdicepos roll( tdicepos pos, int dir ){
tdicepos res;
switch ( dir ){
case UP : res.top = pos.front;
res.front = 7-pos.top;
break;
case DOWN : res.top = 7-pos.front;
res.front = pos.top;
break;
case RIGHT:
case LEFT : res.front = pos.front;
switch ( pos.front ){
case 6:
case 1: switch ( pos.top ){
case 2: res.top = 4; break;
case 3: res.top = 2; break;
case 4: res.top = 5; break;
case 5: res.top = 3; break;
}
break;
case 5:
case 2: switch ( pos.top ){
case 1: res.top = 3; break;
case 3: res.top = 6; break;
case 4: res.top = 1; break;
case 6: res.top = 4; break;
}
break;
case 4:
case 3: switch ( pos.top ){
case 1: res.top = 5; break;
case 2: res.top = 1; break;
case 5: res.top = 6; break;
case 6: res.top = 2; break;
}
break;
}
if ( pos.front > 3 ) res.top = 7 - res.top;
if ( dir == RIGHT ) res.top = 7 - res.top;
break;
}
return res;
}

bool havepass( int x, int y, tdicepos pos ){
for ( int i = 0; i < stackcnt; i ++ ){
if ( stack.row == x && stack.col == y && stack.pos.front == pos.front && stack.pos.top == pos.top )
return true;
}
return false;
}

void findpath( int x, int y, tdicepos dicepos ){
if ( foundpath ) return;

if ( havepass(x, y, dicepos) ) return;
if ( x == posx && y == posy && stackcnt > 0 ){
foundpath = true;
cnt = stackcnt;
return;
}

stack[stackcnt].row = x;
stack[stackcnt].col = y;
stack[stackcnt].pos.front = dicepos.front;
stack[stackcnt].pos.top = dicepos.top;
stackcnt++;

if ( x > 0 && (board[x-1][y] == dicepos.top || board[x-1][y] == -1))
findpath( x-1, y, roll( dicepos, UP ) );
if ( y > 0 && (board[x][y-1] == dicepos.top || board[x][y-1] == -1))
findpath( x, y-1, roll( dicepos, LEFT ) );
if ( x < r-1 && (board[x+1][y] == dicepos.top || board[x+1][y] == -1))
findpath( x+1, y, roll( dicepos, DOWN ) );
if ( y < c-1 && (board[x][y+1] == dicepos.top || board[x][y+1] == -1))
findpath( x, y+1, roll( dicepos, RIGHT ) );
stackcnt--;
}

int main(void){
char mazename[30];
for ( cin >> mazename ; strcmp( mazename, "END" ) != 0; cin >> mazename ){
tdicepos initpos;
cin >> r >> c >> posx >> posy >> initpos.top >> initpos.front;
for ( int i = 0; i < r; i ++ )
for ( int j = 0; j < c; j ++ )
cin >> board[j];

stackcnt = 0, foundpath = false;
findpath( --posx, --posy, initpos );

cout << mazename << endl;
if ( !foundpath ) cout << " No Solution Possible" << endl;
else{
for ( int i = 0; i < cnt; i ++ ){
if ( i % 9 == 0 ) cout << " ";
cout << "(" << stack.row+1 << "," << stack.col+1 << "),";
if ( i % 9 == 8 ) cout << endl;
}
if ( cnt % 9 == 0 ) cout << " ";
else cout << "(" << posx+1 << "," << posy+1 << ")" << endl;
}
}
return 0;
}
[/cpp]
-mk

Post Reply

Return to “Volume 8 (800-899)”