Re: 101 - The Blocks Problem
Posted: Sat Apr 25, 2015 5:06 pm
never mind, I realized that it was due to the condition "if a and b are on the same stack then do nothing".
Code: Select all
#include<iostream>
#include<string.h>
#include <algorithm>
#include<cstdio>
#define D(x) cout<<#x<<" is "<<x<<endl;
using namespace std;
int Location[30][30];
int Lego_location[30],Location_Lego_num[30];
int Legonum;
void clear_onto(int n)
{
int n_now_location = Lego_location[n];
while(Location[n_now_location][Location_Lego_num[n_now_location]-1]!=n)
{
int tmp_lego = Location[n_now_location][Location_Lego_num[n_now_location]-1];
Location_Lego_num[tmp_lego]++;
Location[tmp_lego][Location_Lego_num[tmp_lego]-1]=tmp_lego;
Lego_location[tmp_lego]=tmp_lego;
Location[n_now_location][Location_Lego_num[n_now_location]-1]=-1;
Location_Lego_num[n_now_location]--;
}
return;
}
void move_a_to_b(int a,int b)
{
int a_now_location = Lego_location[a] , b_now_location = Lego_location[b];
int c=0;
for(int i=0;i<Location_Lego_num[a_now_location];i++)
{
if(Location[a_now_location][i]==a) c=1;
if(c!=0)
{
Location_Lego_num[b_now_location]++;
Location[b_now_location][Location_Lego_num[b_now_location]-1] = Location[a_now_location][i];
Lego_location[Location[a_now_location][i]]=b_now_location;
Location[a_now_location][i]=-1;
if(c!=1) c++;
}
}
Location_Lego_num[a_now_location] -= c;
return;
}
int main()
{
int a,b;
string act,act2;
while(cin>>Legonum && Legonum!=EOF)
{
memset(Location,-1,sizeof(Location));
for(int i=0;i<Legonum;i++)
{
Lego_location[i]=i;
Location[i][0]=i;
Location_Lego_num[i]=1;
}
while(cin>>act && act[0]!='q')
{
cin>>a>>act2>>b;
if(a==b || Lego_location[a]== Lego_location[b]) continue;
if(act[0]=='m') clear_onto(a);
if(act2[1]=='n') clear_onto(b);
move_a_to_b(a,b);
}
for(int i=0;i<Legonum;i++)
{
cout<<i<<":";
for(int j=0;j<Location_Lego_num[i];j++)
if(Location[i][j]!=-1) cout<<" "<<Location[i][j];
cout<<endl;
}
}
return 0;
}
Code: Select all
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
int position[30][2];
int block[30][30];
int top[30];
int n;
char action1[10], action2[10];
int a, b, ax, ay, bx, by;
while( scanf( "%d", &n ) != EOF ){
for( int i = 0 ; i < n ; i++ ){
position[i][0] = i;
position[i][1] = 0;
block[i][0] = i;
top[i] = 1;
}
while( scanf( "%s", action1 ) != EOF && strcmp( action1, "quit" ) ){
scanf( "%d%s%d", &a, action2, &b );
ax = position[a][0];
ay = position[a][1];
bx = position[b][0];
by = position[b][1];
if( ax == bx ) continue;
if( !strcmp(action1, "move") ){
for( int i = ay+1 ; i < top[ax] ; i++ ){
position[block[ax][i]][0] = block[ax][i];
position[block[ax][i]][1] = top[block[ax][i]];
block[block[ax][i]][top[block[ax][i]]++] = block[ax][i];
}
top[ax] = ay+1;
}
if( !strcmp(action2, "onto") ){
for( int i = by+1 ; i < top[bx] ; i++ ){
position[block[bx][i]][0] = block[bx][i];
position[block[bx][i]][1] = top[block[bx][i]];
block[block[bx][i]][top[block[bx][i]]++] = block[bx][i];
}
top[bx] = by+1;
}
for( int i = ay ; i < top[ax] ; i++ ){
position[block[ax][i]][0] = bx;
position[block[ax][i]][1] = top[bx];
block[bx][top[bx]++] = block[ax][i];
}
top[ax] = ay;
}
for( int i = 0 ; i < n ; i++ ){
printf( "%d:", i );
for( int j = 0 ; j < top[i] ; j++ )
printf( " %d", block[i][j] );
printf( "\n" );
}
}
return 0;
}
Code: Select all
#include<stdio.h>
#include<stdlib.h>
int main()
{
/*Variable declarations*/
int n, i, j;
char command[4];
int moveFlag, pileFlag, ontoFlag, overFlag, failFlag;
int a, b, aXPos, aYPos, bXPos, bYPos, returnPos;
int blockPos[25][25];
scanf("%d",&n);
/*First input is number of blocks*/
/*Initially the positions of the blocks
are corresponding to the array positions*/
for(i=0;i<n;i++)
{
blockPos[i][0]=i;
blockPos[i][1]=-1;
}
/*Keep on fetching commands till quit is encountered*/
while(1)
{
aXPos=-1;
aYPos=-1;
bXPos=-1;
bYPos=-1;
failFlag=0;
overFlag=0;
ontoFlag=0;
moveFlag=0;
pileFlag=0;
/*Take in the first command*/
scanf("%s",command);
/*Set flag as per command selected*/
if(command[0]=='m')
moveFlag=1;
else if(command[0]=='p')
pileFlag=1;
else if(command[0]=='q')
break;
else
{
failFlag=1;
break;
}
/*Accept the value of a*/
scanf("%d",&a);
/*Accept the second command*/
scanf("%s",command);
/*Set flag as per command selected*/
if(command[1]=='v')
overFlag=1;
else if(command[1]=='n')
ontoFlag=1;
else
{
failFlag=1;
break;
}
/*Accept value of b*/
scanf("%d",&b);
if(a>=n||b>=n||a<0||b<0) continue;
if(a==b) continue;
/*Find out position of a and b*/
for(i=0;i<n;i++)
for(j=0;blockPos[i][j]!=-1;j++)
{
if(blockPos[i][j]==a)
{
aXPos=i;
aYPos=j;
}
else if(blockPos[i][j]==b)
{
bXPos=i;
bYPos=j;
}
}
/*printf("%d %d %d %d\n",aXPos,aYPos, bXPos, bYPos);*/
if(aXPos==bXPos)
continue;
/*There are three operations performed by the arm:
1. empty post a (move onto, move over)
2. empty post b (move onto, pile onto)
3. move a after b*/
/*Empty post a if operation is not pile*/
if(!pileFlag){
for(i=aYPos+1;blockPos[aXPos][i]!=-1;i++)
{
returnPos = blockPos[aXPos][i];
blockPos[aXPos][i]=-1;
blockPos[returnPos][0] = returnPos;
blockPos[returnPos][1] = -1;
}
/*blockPos[aXPos][aYPos+1]=-1; */
}
/*Empty post b if operation is not over*/
if(!overFlag){
for(i=bYPos+1;blockPos[bXPos][i]!=-1;i++)
{
returnPos = blockPos[bXPos][i];
blockPos[bXPos][i]=-1;
blockPos[returnPos][0] = returnPos;
blockPos[returnPos][1] = -1;
}
/*blockPos[bXPos][bYPos+1]=-1;*/
}
/*Move a after b*/
/*move to end of b*/
for(i=bYPos;blockPos[bXPos][i]!=-1;i++);
bYPos=i-1;
for(i=aYPos;blockPos[aXPos][i]!=-1;i++)
{
blockPos[bXPos][++bYPos]=blockPos[aXPos][i];
blockPos[aXPos][i] = -1;
/*printf("%d\n",blockPos[bXPos][bYPos]);*/
}
blockPos[bXPos][bYPos+1]=-1;
};
if(failFlag==1)
{
/*do nothing*/
}
else
{
/*display*/
for(i=0;i<n;i++)
{
printf("%d:",i);
for(j=0;blockPos[i][j]!=-1;j++)
printf(" %d",blockPos[i][j]);
printf("\n");
}
}
return 0;
}
Code: Select all
#include <stdio.h>
#include <string.h>
void move_onto(int,int,int);
void move_over(int,int,int);
void pile_onto(int,int,int);
void pile_over(int,int,int);
void display(int);
int ar[25][25];
int main()
{
int n,a,b,i,j;
scanf("%d",&n);
char s1[5],s2[5];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
ar[i][j]=-1;
for(i=0;i<n;i++)
ar[i][0]=i;
while(scanf("%s",s1)==1) {
if(strcmp(s1,"quit")==0 )
display(n);
else
scanf("%d%s%d",&a,s2,&b);
if(a==b || a>=n || b>=n) continue;
else if(strcmp(s1,"move")==0 && strcmp(s2,"onto")==0)
move_onto(n,a,b);
else if(strcmp(s1,"move")==0 && strcmp(s2,"over")==0)
move_over(n,a,b);
else if(strcmp(s1,"pile")==0 && strcmp(s2,"onto")==0)
pile_onto(n,a,b);
else if(strcmp(s1,"pile")==0 && strcmp(s2,"over")==0)
pile_over(n,a,b);
else
continue;
}
}
void move_onto(int n,int a,int b)
{
int i,j,p,q,x,y,h,a1,a2,x1;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(ar[i][j]==a)
{
x=i;
y=j;
break;
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(ar[i][j]==b)
{
p=i;
q=j;
break;
}
}
if(x==p) return ;
for(i=y+1;i<n;i++)
{
j=ar[x][i];
if(j>=0)
{
ar[j][0]=j;
ar[x][i]=-1;
}
else if(j==-1) break;
}
for(i=q+1;i<n;i++)
{
j=ar[p][i];
if(j>=0)
{
ar[j][0]=j;
ar[p][i]=-1;
}
else if(j=-1) break;
}
ar[p][q+1]=ar[x][y];
ar[x][y]=-1;
}
void move_over(int n,int a,int b)
{
int i,j,p,q,x,y,h,a1,a2,y1;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(ar[i][j]==a)
{
x=i;
y=j;
break;
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(ar[i][j]==b)
{
p=i;
q=j;
break;
}
}
if(x==p) return ;
for(i=y+1;i<n;i++)
{
j=ar[x][i];
if(j>=0)
{
ar[j][0]=j;
ar[x][i]=-1;
}
else if(j==-1) break;
}
for(i=q+1;i<n;i++)
{
if(ar[p][i]==-1)
{
ar[p][i]=ar[x][y];
ar[x][y]=-1;
break;
}
}
}
void pile_onto(int n,int a,int b)
{
int i,j,p,q,x,y,h,a1,a2,y1,x1;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(ar[i][j]==a)
{
x=i;
y=j;
break;
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(ar[i][j]==b)
{
p=i;
q=j;
break;
}
}
if(x==p) return ;
for(i=q+1;i<n;i++)
{
j=ar[p][i];
if(j>=0)
{
ar[j][0]=j;
ar[p][i]=-1;
}
else if(j==-1) break;
}
j=q+1;
for(i=y;i<n;i++)
{
if((ar[x][i]>=0) && (ar[p][j]==-1))
{
ar[p][j]=ar[x][i];
ar[x][i]=-1;
j++;
}
else break;
}
}
void pile_over(int n,int a,int b)
{
int i,j,p,q,x,y,h,a1,a2,y1;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(ar[i][j]==a)
{
x=i;
y=j;
break;
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(ar[i][j]==b)
{
p=i;
q=j;
break;
}
}
if(x==p) return ;
for(i=y;i<n;i++)
for(j=q+1;j<n;j++)
{
if(ar[x][i]!=-1)
{
if(ar[p][j]==-1) {
ar[p][j]=ar[x][i];
ar[x][i]=-1;
}
}
else if(ar[x][i]==-1) break;
}
}
void display(int n)
{
int i,j;
for(j=0;j<n;j++)
{
printf("\n%d: ",j);
for(i=0;i<n;i++)
{
if(ar[j][i]!=-1)
printf("%d ",ar[j][i]);
}
}
printf("\n");
main();
}
Code: Select all
#include <stdio.h>
#include <string.h>
int world[25][25];
int size = 0;
void quit();
void moveOnto(int a, int b);
void moveOver(int a, int b);
void pileOnto(int a, int b);
void pileOver(int a, int b);
void clearAbove(int i, int j);
void initWorld();
int checkSameStacks(int a, int b);
int main()
{
char cmd1[10], cmd2[10];
int p1, p2;
scanf("%d", &size);
initWorld();
while (scanf("%s", cmd1)){
if(strcmp(cmd1, "quit") == 0){ /*quit*/
quit();
break;
}
else{
scanf("%d", &p1);
scanf("%s", cmd2);
scanf("%d", &p2);
if (p1 == p2) continue;
if (p1 >= size || p2 >= size || p1<0 || p2<0) continue;
if (checkSameStacks(p1, p2)==0) continue;
/*Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command.
All illegal commands should be ignored and should have no affect on the configuration of blocks.*/
if (strcmp(cmd1,"move") == 0){ /*move*/
if (strcmp(cmd2,"onto") == 0){ /*onto*/
moveOnto(p1, p2);
}
else{ /*over*/
moveOver(p1, p2);
}
}
else{ /*pile*/
if (strcmp(cmd2,"onto") == 0){ /*onto*/
pileOnto(p1, p2);
}
else{ /*over*/
pileOver(p1, p2);
}
}
}
}
return 0;
}
void quit(){
/*If there is at least a block on it, the colon must be followed by one space,
followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space.
Don't put any trailing spaces on a line.*/
int i, j;
for (i = 0; i < size; i++){
printf("%d:", i);
for (j = 0; j < size; j++){
if (world[i][j] == -1) break;
printf(" %d", world[i][j]);
}
printf("\n");
}
return;
}
void moveOnto(int a, int b){
/*puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.*/
int i=-1, j=-1, i_a=-1, j_a=-1, i_b=-1, j_b=-1;
for (i = 0; i < size; i++){
for (j = 0; j < size; j++){/*search for the two blocks*/
if (world[i][j] == a){
i_a = i;
j_a = j;
}
if (world[i][j] == b){
i_b = i;
j_b = j;
}
}
if ((i_a != -1) && (i_b != -1)){
if (i_a == i_b) return;/*if they are in the same stack, do nothing and return*/
else{/*otherwise clear it*/
clearAbove(i_a, j_a);
clearAbove(i_b, j_b);
}
break;
}
}
/*The program should only arrive here if the command is valid
Put block a onto block b, clear block a from its previous place and finish the command*/
world[i_b][j_b + 1] = world[i_a][j_a];
world[i_a][j_a] = -1;
return;
}
void moveOver(int a, int b){
/* puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.*/
int i = -1, j = -1, i_a = -1, j_a = -1, i_b = -1, j_b = -1;
for (i = 0; i < size; i++){
for (j = 0; j < size; j++){/*search for the two blocks*/
if (world[i][j] == a){
i_a = i;
j_a = j;
}
if (world[i][j] == b){
i_b = i;
j_b = j;
}
}
if ((i_a != -1) && (i_b != -1)){
if (i_a == i_b) return;/*if they are in the same stack, do nothing and return*/
else{/*otherwise clear it*/
clearAbove(i_a, j_a);
}
break;
}
}
/*The program should only arrive here if the command is valid
Put block a over block b, clear block a from its previous place and finish the command*/
while (j_b < size){
if (world[i_b][j_b] == -1){
world[i_b][j_b] = world[i_a][j_a];
world[i_a][j_a] = -1;
return;
}
j_b++;
}
/*If it arrives here, something is messed up :)*/
printf("Kaki van :)");
return;
}
void pileOnto(int a, int b){
/*moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b.
All blocks on top of block b are moved to their initial positions prior to the pile taking place.
The blocks stacked above block a retain their order when moved.*/
int i = -1, j = -1, i_a = -1, j_a = -1, i_b = -1, j_b = -1;
for (i = 0; i < size; i++){
for (j = 0; j < size; j++){/*search for the two blocks*/
if (world[i][j] == a){
i_a = i;
j_a = j;
}
if (world[i][j] == b){
i_b = i;
j_b = j;
}
}
if ((i_a != -1) && (i_b != -1)){
if (i_a == i_b) return;/*if they are in the same stack, do nothing and return*/
else{/*otherwise clear it*/
clearAbove(i_b, j_b);
}
break;
}
}
/*The program should only arrive here if the command is valid
Pile the stack of block a onto block b, clear the stack of block a from its previous place and finish the command*/
j_b++;
while (j_a < size && j_b < size){
world[i_b][j_b] = world[i_a][j_a];
world[i_a][j_a] = -1;
j_a++;
j_b++;/*possible out of bounds?*/
}
return;
}
void pileOver(int a, int b){
/*puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b.
The blocks stacked above block a retain their original order when moved.*/
int i = -1, j = -1, i_a = -1, j_a = -1, i_b = -1, j_b = -1;
for (i = 0; i < size; i++){
for (j = 0; j < size; j++){/*search for the two blocks*/
if (world[i][j] == a){
i_a = i;
j_a = j;
}
if (world[i][j] == b){
i_b = i;
j_b = j;
}
}
if ((i_a != -1) && (i_b != -1)){
if (i_a == i_b) return;/*if they are in the same stack, do nothing and return*/
break;
}
}
/*The program should only arrive here if the command is valid
Pile the stack of block a over the stack of block b, clear the stack of block a from its previous place and finish the command*/
while (j_b < size && world[i_b][j_b] != -1){/*search for the first available place in the stack of block b*/
j_b++;
}
while (j_a < size && j_b < size){
world[i_b][j_b] = world[i_a][j_a];
world[i_a][j_a] = -1;
j_a++;
j_b++;
}
return;
}
int checkSameStacks(int a, int b){
int i, j, stackA = -1, stackB = -1;
for (i = 0; i < size; i++){
for (j = 0; j < size; j++){
if (world[i][j] == a) stackA = i;
if (world[i][j] == b) stackB = i;
if (stackA != -1 && stackB != -1){
if (stackA == stackB) return 0;
else return 1;
}
};
}
return 0;
}
void clearAbove(int i, int j){
int value;
if (j < size){
for (++j; j < size; j++){
value = world[i][j];
world[value][0] = value;
world[i][j] = -1;
}
}
}
void initWorld(){
int i, j;
for (i = 0; i < size; i++){
world[i][0] = i;
for (j = 1; j < size; j++){
world[i][j] = -1;
}
}
return;
}