101 - The Blocks Problem

[brianfry713]

First search for existing threads. Post to an existing thread if you can't figure out your problem so there won't be 139 threads about the same problem.
http://acm.uva.es/board/search.php?keyw ... &sr=topics
Then try the I/O posted there against your code. Your code fails for this I/O:
http://acm.uva.es/board/viewtopic.php?t=70902
You can also generate I/O at:
http://www.uvatoolkit.com/problemssolve.php

[gsingh93]

I'm getting a WA on problem 101. I'll paste my code and some sample inputs and outputs.

Code: Select all

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

class Main {

	private static Map<Integer, Integer> posMap = new HashMap<Integer, Integer>();
	private static List<Integer> lists[];

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		// Initialize the data structures
		int n = scanner.nextInt();
		lists = new LinkedList[n];
		for (int i = 0; i < n; i++) {
			posMap.put(i, i);
			lists[i] = new LinkedList<Integer>();
			lists[i].add(i);
		}

		// Parse the input
		while (scanner.hasNext()) {
			String w1 = scanner.next();
			if (w1.equals("quit"))
				break;

			int n1 = scanner.nextInt();
			String w2 = scanner.next();
			int n2 = scanner.nextInt();
			
			if (n1 == n2 || posMap.get(n1) == posMap.get(n2))
				continue;

			if (w1.equals("move")) {
				if (w2.equals("onto")) {
					moveOnto(n1, n2);
				} else if (w2.equals("over")) {
					moveOver(n1, n2);
				}
			} else if (w1.equals("pile")) {
				if (w2.equals("onto")) {
					pileOnto(n1, n2);
				} else if (w2.equals("over")) {
					pileOver(n1, n2);
				}
			}
		}

		printBlockPositions();
	}

	/**
	 * Moves block a onto block b after returning any blocks on top of a and b
	 * to their initial positions
	 */
	private static void moveOnto(int a, int b) {
		clearStack(b);
		clearStack(a);

		move(a, b);
	}

	/**
	 * Moves block a onto the top of the stack containing block b, returning any
	 * blocks on top of a to their original positions
	 */
	private static void moveOver(int a, int b) {
		clearStack(a);
		move(a, b);
	}
	
	/**
	 * Moves block a and any blocks above block a on top of block b
	 */
	private static void pileOnto(int a, int b) {
		clearStack(b);
		movePile(a, b);
	}
	
	/**
	 * Moves block a and any blocks above block a on top of the stack containing
	 * block b
	 * 
	 */
	private static void pileOver(int a, int b) {
		movePile(a, b);
	}

	/**
	 * Prints the positions of all the blocks
	 */
	private static void printBlockPositions() {
		for (int i = 0; i < lists.length; i++) {
			List<Integer> list = lists[i];
			System.out.print(i + ":");
			if (!list.isEmpty())
				System.out.print(" ");
			for (int j = 0; j < list.size(); j++) {
				System.out.print(list.get(j));
				if (j != list.size() - 1) {
					System.out.print(" ");
				}
			}
			if (i != lists.length - 1)
				System.out.println("");
		}
	}

	/**
	 * Returns the blocks in the stack above the sentinel to their original
	 * locations
	 */
	private static void clearStack(int sentinel) {
		int col = posMap.get(sentinel);

		while (!lists[col].isEmpty()) {
			// Get the top block in the same column as block b
			int block = lists[col].get(lists[col].size() - 1);
			if (block != sentinel)
				resetBlock(block);
			else
				return;
		}
	}

	/**
	 * Puts a block back in its original location
	 */
	private static void resetBlock(Integer block) {
		lists[posMap.get(block)].remove(block);
		posMap.put(block, block);
		lists[block].add(block);
	}

	/**
	 * Moves block a to the stack containing block b
	 */
	private static void move(int a, int b) {
		int posA = posMap.get(a);
		int posB = posMap.get(b);

		lists[posA].remove(Integer.valueOf(a));
		posMap.put(a, posB);
		lists[posB].add(a);
	}

	/**
	 * Moves the pile above block a to the stack containing block b
	 */
	private static void movePile(int a, int b) {
		List<Integer> list = lists[posMap.get(a)];
		List<Integer> tempList = list.subList(list.indexOf(a), list.size());
		List<Integer> subList = new LinkedList<Integer>(tempList);

		tempList.clear();

		Integer pos = posMap.get(b);
		lists[pos].addAll(subList);
		for (Integer integer : subList) {
			posMap.put(integer, pos);
		}
	}
}

Input 1

Code: Select all

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

Output 1

Code: Select all

0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

Input 2

Code: Select all

21
move 2 onto 1
move 3 onto 2
move 4 onto 3
move 5 over 1
pile 1 over 10
move 9 over 8
move 11 over 8
pile 3 over 8
pile 8 over 3
move 20 over 19
pile 19 over 18
pile 18 onto 15
move 15 over 3
pile 20 onto 19
pile 19 onto 18
pile 18 over 17
quit

Output 2

Code: Select all

0: 0
1:
2:
3:
4:
5:
6: 6
7: 7
8: 8 9 11 3 4 5 15
9:
10: 10 1 2
11:
12: 12
13: 13
14: 14
15:
16: 16
17: 17 18 19 20
18:
19:
20:

[Sabiha_Fancy]

I am getting wrong answer each time i tried to submit it. If any one kindly help me to find out the problem i will be glad.
Here is my code
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>

#define SIZE 25

int table[SIZE];

void createlist(int n);
void move_onto(int box1,int box2,int n);
void move_over(int box1,int box2,int n);
void pile_onto(int box1,int box2,int n);
void pile_over(int box1,int box2,int n);
void print(int n);

struct node {
int value;
struct node *next;
};

struct node *a[SIZE];

int main()
{
int k,box1,box2;
char com1[6];
char com2[6];
int n;
scanf("%d",&n);
createlist(n);
while(1)
{
fflush(stdin);
scanf("%s",com1);
if(strcmp(com1,"quit")==0)
break;
scanf("%d %s %d",&box1,com2,&box2);
fflush(stdin);
if((box1 != box2) && (table[box1] != table[box2]))
{
if(strcmp(com1,"move") == 0)
{
if(strcmp(com2,"onto") == 0)
{
move_onto(box1,box2,n);
}
else
{
move_over(box1,box2,n);
}
}
else
{
if(strcmp(com2,"onto") == 0)
{
pile_onto(box1,box2,n);
}
else
{
pile_over(box1,box2,n);
}
}
}
}
print(n);
return 0;
}

void print(int n)
{
struct node *head;
int i;
for(i=0; i<n; ++i)
{
head = a;
head = head->next;
printf("%d:",i);
while(head != NULL)
{
printf(" %d",head->value);
head = head->next;
}
if(head == NULL)
printf("\n");
}
}

void createlist(int n)
{
int i;
struct node *p;
for(i=0; i<n; ++i)
{
a = (struct node *) malloc(sizeof(struct node));
a->value = i;
p = (struct node *) malloc(sizeof(struct node));
p->value = i;
p->next = NULL;
a->next = p;
table = i;
}
}

void move_onto(int box1,int box2,int n)
{
struct node *p,*q,*head;
int tvalue1,tvalue2;
tvalue1 = table[box1];

head = a[tvalue1];
q = head;
head = head->next;
while((head->value != box1) && (head != NULL))
{
head = head->next;
q = q->next;
}
if((head != NULL) && (head->value == box1))
{
p = head;
q->next = head->next;
}
tvalue2 = table[box2];
head = a[tvalue2];
head = head->next;
while((head->value != box2) && (head != NULL))
{
head = head->next;
}
if((head != NULL) && (head->value == box2))
{
p->next = head->next;
head->next = p;
table[box1] = tvalue2;
}
}

void move_over(int box1,int box2,int n)
{
struct node *p,*q,*head;
int tvalue1,tvalue2,flag = 0;
tvalue1 = table[box1];

head = a[tvalue1];
q = head;
head = head->next;
while((head->value != box1) && (head != NULL))
{
head = head->next;
q = q->next;
}
if((head != NULL) && (head->value == box1))
{
p = head;
q->next = head->next;
}
tvalue2 = table[box2];
head = a[tvalue2];
q = head;
head = head->next;
while(head != NULL)
{
if(head->value == box2)
flag = 1;
head = head->next;
q = q->next;
}
if(head == NULL && flag == 1)
{
p->next = head;
q->next = p;
table[box1] = tvalue2;

}
}

void pile_onto(int box1,int box2,int n)
{
struct node *p,*q,*head,*tail,*front;
int tvalue1,tvalue2,flag1=0;

tvalue1 = table[box1];
head = a[tvalue1];
q = head;
front = q;
head = head->next;
while(head != NULL)
{
if(head->value == box1)
{
p = head;
front = q;
flag1 = 1;
}
head = head->next;
q = q->next;
if(head == NULL)
{
tail = q;
}
}

if(head == NULL)
front->next = head;

tvalue2 = table[box2];
head = a[tvalue2];
q = head;
head = head->next;
while((head != NULL) && (head->value != box2))
{
head = head->next;
}
if((head != NULL) && (flag1 == 1) && (head->value == box2))
{
tail->next = head->next;
head->next = p;
while(p != tail->next)
{
table[p->value] = tvalue2;
p = p->next;
}
}
}

void pile_over(int box1,int box2,int n)
{
struct node *p,*q,*head,*tail,*front;
int tvalue1,tvalue2,flag=0,flag1=0;

tvalue1 = table[box1];
head = a[tvalue1];
q = head;
front = q;
head = head->next;
while(head != NULL)
{
if(head->value == box1)
{
p = head;
front = q;
flag1 = 1;
}
head = head->next;
q = q->next;
if(head == NULL)
{
tail = q;
}
}

if(head == NULL)
front->next = head;

tvalue2 = table[box2];
head = a[tvalue2];
q = head;
head = head->next;
while(head != NULL)
{
if(head->value == box2)
flag = 1;
head = head->next;
q = q->next;
}
if((flag == 1) && (flag1 == 1)&& (head == NULL))
{
q->next = p;
tail->next = NULL;
while(p != tail->next)
{
table[p->value] = tvalue2;
p = p->next;
}
}
}

[brianfry713]

Try the I/O posted at:
http://acm.uva.es/board/viewtopic.php?t=4019

[brianfry713]

Are you printing a newline at the end of the last line of the output?

[gsingh93]

I have this code:

Code: Select all

if (i != lists.length - 1)
            System.out.println("");

Which should print a newline.

[Sabiha_Fancy]

Thank you

[brianfry713]

Doesn't that print a newline at the end of each line except the last one?

[Atkins]

my code

Code: Select all

#include <iostream>
#include <vector>

class Block {
public:
    Block(int n);
    int number;
    Block * next;
};

class Block_world {
public:
    Block_world(int n);
    std::vector<Block*> world;
    void print();
    Block * search(int const num);
    int search_pile(int const num);
    void null_pre(int const num);
    void moveonto(int const a, int const b);
    void moveover(int const a, int const b);
    void pileonto(int const a, int const b);
    void pileover(int const a, int const b);
    void return_block(Block * const ptr);
};

Block::Block(int n)
:number(n), next(NULL)
{
}

Block_world::Block_world(int n)
{
    for (int i=0; i<n; i++) {
        Block * tmp;
        tmp=new Block(i);
        world.push_back(tmp);
    }
}

void Block_world::print()
{
    int size=(int)world.size();
    Block * ptr=NULL;
    for (int i=0; i<size; i++) {
        ptr=world.at(i);
        std::cout << i << ":";
        while (ptr!=NULL) {
            std::cout << " " << ptr->number ;
            ptr=ptr->next;
        }
        std::cout << std::endl;
    }
    
}

Block * Block_world::search(int const num)
{
    Block * now = NULL;
    for (int i=0; i<world.size(); i++) {
        now=world.at(i);
        if (now!=NULL) {
            if (now->number==num) {
                return now;
            }
            while (now->next!=NULL) {
                now=now->next;
                if (now->number==num) {
                    return now;
                }
            }
        }
    }
    return now;
}

int Block_world::search_pile(int const num)
{
    Block * now = NULL;
    for (int i=0; i<world.size(); i++) {
        now=world.at(i);
        if (now!=NULL) {
            if (now->number==num) {
                return i;
            }
            while (now->next!=NULL) {
                now=now->next;
                if (now->number==num) {
                    return i;
                }
            }
        }
    }
    return -1;
}

void Block_world::null_pre(int const num)
{
    
    Block * now = NULL, * pre = NULL;
    for (int i=0; i<world.size(); i++) {
        now=world.at(i);
        if (now!=NULL) {
            if (now->number==num) {
                world.at(i)=NULL;
                return;
            }
            pre=now;
            now=pre->next;
            while (now!=NULL) {
                if (now->number==num) {
                    pre->next=NULL;
                    return;
                }
                pre=pre->next;
                now=now->next;
            }
        }
    }
}

void Block_world::moveonto(int const a, int const b)
{
    Block * aPtr, * bPtr;
    if (search_pile(a)==search_pile(b)) {
        return;
    }
    aPtr=search(a);
    bPtr=search(b);
    null_pre(a);
    return_block(aPtr->next);
    return_block(bPtr->next);
    aPtr->next=NULL;
    bPtr->next=aPtr;
}

void Block_world::moveover(int const a, int const b)
{
    Block * aPtr, * b_pilePtr;
    aPtr=search(a);
    b_pilePtr=world.at(search_pile(b));
    null_pre(a);
    return_block(aPtr->next);
    while (b_pilePtr->next!=NULL) {
        b_pilePtr=b_pilePtr->next;
    }
    aPtr->next=NULL;
    b_pilePtr->next=aPtr;
}

void Block_world::pileonto(int const a, int const b)
{
    Block * aPtr, * bPtr;
    if (search_pile(a)==search_pile(b)) {
        return;
    }
    aPtr=search(a);
    null_pre(a);
    bPtr=search(b);
    return_block(bPtr->next);
    bPtr->next=aPtr;
}

void Block_world::pileover(int const a, int const b)
{
    Block * aPtr, * pos;
    int b_pile;
    aPtr=search(a);
    b_pile=search_pile(b);
    null_pre(a);
    if (world.at(b_pile)==NULL) {
        world.at(b_pile)=aPtr;
        return;
    }
    pos=world.at(b_pile);
    while (pos->next!=NULL) {
        pos=pos->next;
    }
    pos->next=aPtr;
}

void Block_world::return_block(Block * const ptr)
{
    Block * now=ptr;
    Block * next=NULL;
    while (now!=NULL) {
        next=now->next;
        
        if (world.at(now->number)!=NULL) {
            std::cout << "\nerror\n";
        }
        world.at(now->number)=now;
        now->next=NULL;
        now=next;
    }
}

int main(int argc, const char * argv[])
{           
    int size, a, b;
    char inst1[5], inst2[5];
    std::cin >> size;
    Block_world i (size);
    while (std::cin >> inst1 ) {
        if (inst1[0]=='q'&&inst1[1]=='u'&&inst1[2]=='i'&&inst1[3]=='t') {
            i.print();
            return 0;
        }
        else {
            std::cin >> a >> inst2 >> b;
            if (inst1[0]=='m'&&inst1[1]=='o'&&inst1[2]=='v'&&inst1[3]=='e') {
                if (inst2[0]=='o'&&inst2[1]=='n'&&inst2[2]=='t'&&inst2[3]=='o') {
                    i.moveonto(a, b);
                } else if (inst2[0]=='o'&&inst2[1]=='v'&&inst2[2]=='e'&&inst2[3]=='r') {
                    i.moveover(a, b);
                }
            } else if (inst1[0]=='p'&&inst1[1]=='i'&&inst1[2]=='l'&&inst1[3]=='e') {
                if (inst2[0]=='o'&&inst2[1]=='n'&&inst2[2]=='t'&&inst2[3]=='o') {
                    i.pileonto(a, b);
                } else if (inst2[0]=='o'&&inst2[1]=='v'&&inst2[2]=='e'&&inst2[3]=='r') {
                    i.pileover(a, b);
                }
            }
        }
    }
    //std::cout << "Hello, World!\n";
    return 0;
}

I try lots of test data on my program and it works!
But still got RE
Can anyone help me

[Atkins]

my code

Code: Select all

#include <iostream>
#include <vector>

class Block {
public:
    Block(int n);
    int number;
    Block * next;
};

class Block_world {
public:
    Block_world(int n);
    std::vector<Block*> world;
    void print();
    Block * search(int const num);
    int search_pile(int const num);
    void null_pre(int const num);
    void moveonto(int const a, int const b);
    void moveover(int const a, int const b);
    void pileonto(int const a, int const b);
    void pileover(int const a, int const b);
    void return_block(Block * const ptr);
};

Block::Block(int n)
:number(n), next(NULL)
{
}

Block_world::Block_world(int n)
{
    for (int i=0; i<n; i++) {
        Block * tmp;
        tmp=new Block(i);
        world.push_back(tmp);
    }
}

void Block_world::print()
{
    int size=(int)world.size();
    Block * ptr=NULL;
    for (int i=0; i<size; i++) {
        ptr=world.at(i);
        std::cout << i << ":";
        while (ptr!=NULL) {
            std::cout << " " << ptr->number ;
            ptr=ptr->next;
        }
        std::cout << std::endl;
    }
    
}

Block * Block_world::search(int const num)
{
    Block * now = NULL;
    for (int i=0; i<world.size(); i++) {
        now=world.at(i);
        if (now!=NULL) {
            if (now->number==num) {
                return now;
            }
            while (now->next!=NULL) {
                now=now->next;
                if (now->number==num) {
                    return now;
                }
            }
        }
    }
    return now;
}

int Block_world::search_pile(int const num)
{
    Block * now = NULL;
    for (int i=0; i<world.size(); i++) {
        now=world.at(i);
        if (now!=NULL) {
            if (now->number==num) {
                return i;
            }
            while (now->next!=NULL) {
                now=now->next;
                if (now->number==num) {
                    return i;
                }
            }
        }
    }
    return -1;
}

void Block_world::null_pre(int const num)
{
    
    Block * now = NULL, * pre = NULL;
    for (int i=0; i<world.size(); i++) {
        now=world.at(i);
        if (now!=NULL) {
            if (now->number==num) {
                world.at(i)=NULL;
                return;
            }
            pre=now;
            now=pre->next;
            while (now!=NULL) {
                if (now->number==num) {
                    pre->next=NULL;
                    return;
                }
                pre=pre->next;
                now=now->next;
            }
        }
    }
}

void Block_world::moveonto(int const a, int const b)
{
    Block * aPtr, * bPtr;
    if (search_pile(a)==search_pile(b)) {
        return;
    }
    aPtr=search(a);
    bPtr=search(b);
    null_pre(a);
    return_block(aPtr->next);
    return_block(bPtr->next);
    aPtr->next=NULL;
    bPtr->next=aPtr;
}

void Block_world::moveover(int const a, int const b)
{
    Block * aPtr, * b_pilePtr;
    aPtr=search(a);
    b_pilePtr=world.at(search_pile(b));
    null_pre(a);
    return_block(aPtr->next);
    while (b_pilePtr->next!=NULL) {
        b_pilePtr=b_pilePtr->next;
    }
    aPtr->next=NULL;
    b_pilePtr->next=aPtr;
}

void Block_world::pileonto(int const a, int const b)
{
    Block * aPtr, * bPtr;
    if (search_pile(a)==search_pile(b)) {
        return;
    }
    aPtr=search(a);
    null_pre(a);
    bPtr=search(b);
    return_block(bPtr->next);
    bPtr->next=aPtr;
}

void Block_world::pileover(int const a, int const b)
{
    Block * aPtr, * pos;
    int b_pile;
    aPtr=search(a);
    b_pile=search_pile(b);
    null_pre(a);
    if (world.at(b_pile)==NULL) {
        world.at(b_pile)=aPtr;
        return;
    }
    pos=world.at(b_pile);
    while (pos->next!=NULL) {
        pos=pos->next;
    }
    pos->next=aPtr;
}

void Block_world::return_block(Block * const ptr)
{
    Block * now=ptr;
    Block * next=NULL;
    while (now!=NULL) {
        next=now->next;
        
        if (world.at(now->number)!=NULL) {
            std::cout << "\nerror\n";
        }
        world.at(now->number)=now;
        now->next=NULL;
        now=next;
    }
}

int main(int argc, const char * argv[])
{           
    int size, a, b;
    char inst1[5], inst2[5];
    std::cin >> size;
    Block_world i (size);
    while (std::cin >> inst1 ) {
        if (inst1[0]=='q'&&inst1[1]=='u'&&inst1[2]=='i'&&inst1[3]=='t') {
            i.print();
            return 0;
        }
        else {
            std::cin >> a >> inst2 >> b;
            if (inst1[0]=='m'&&inst1[1]=='o'&&inst1[2]=='v'&&inst1[3]=='e') {
                if (inst2[0]=='o'&&inst2[1]=='n'&&inst2[2]=='t'&&inst2[3]=='o') {
                    i.moveonto(a, b);
                } else if (inst2[0]=='o'&&inst2[1]=='v'&&inst2[2]=='e'&&inst2[3]=='r') {
                    i.moveover(a, b);
                }
            } else if (inst1[0]=='p'&&inst1[1]=='i'&&inst1[2]=='l'&&inst1[3]=='e') {
                if (inst2[0]=='o'&&inst2[1]=='n'&&inst2[2]=='t'&&inst2[3]=='o') {
                    i.pileonto(a, b);
                } else if (inst2[0]=='o'&&inst2[1]=='v'&&inst2[2]=='e'&&inst2[3]=='r') {
                    i.pileover(a, b);
                }
            }
        }
    }
    //std::cout << "Hello, World!\n";
    return 0;
}

I try lots of test data on my program and it works!
But still got RE
Can anyone help me

[SirHero]

Code: Select all

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int pos[27];
vector<vector<int> > move_onto(vector<vector<int> > v,int a,int b)
{
    if(pos[a]!=pos[b])
    {
        int pos1=pos[a],pos2=pos[b];
        int i;
        for(i=0;v[pos1][i]!=a;++i);
        i++;
        for(;i<v[pos1].size();++i)
        {
            v[v[pos1][i]].push_back(v[pos1][i]);
            pos[v[pos1][i]]=v[pos1][i];
            v[pos1].erase(v[pos1].begin()+i);
            --i;
        }
        for(i=0;v[pos2][i]!=b;++i);
        i++;
        for(;i<v[pos2].size();++i)
        {
            v[v[pos2][i]].push_back(v[pos2][i]);
            pos[v[pos2][i]]=v[pos2][i];
            v[pos2].erase(v[pos2].begin()+i);
            --i;
        }
        v[pos[b]].push_back(a);
        v[pos[a]].erase(v[pos[a]].end()-1);
        pos[a]=pos[b];
    }
    return v;
}
vector<vector<int> > move_over(vector<vector<int> > v,int a,int b)
{
    if(pos[a]!=pos[b])
    {
        int pos1=pos[a],pos2=pos[b];
        int i;
        for(i=0;v[pos1][i]!=a;++i);
        i++;
        for(;i<v[pos1].size();++i)
        {
            v[v[pos1][i]].push_back(v[pos1][i]);
            v[pos1].erase(v[pos1].begin()+i);
            pos[v[pos1][i]]=v[pos1][i];
            --i;
        }
        v[pos[b]].push_back(a);
        v[pos[a]].erase(v[pos[a]].end()-1);
        pos[a]=pos[b];
    }
    return v;
}
vector<vector<int> > pile_onto(vector<vector<int> > v,int a,int b)
{
    if(pos[a]!=pos[b])
    {
        int pos1=pos[a],pos2=pos[b];
        int i;
        for(i=0;v[pos2][i]!=b;++i);
        ++i;
        for(;i<v[pos2].size();++i)
        {
            v[v[pos2][i]].push_back(v[pos2][i]);
            pos[v[pos2][i]]=v[pos2][i];
            v[pos2].erase(v[pos2].begin()+i);
            --i;
        }
        for(i=0;v[pos[a]][i]!=a;++i);
        for(;i<v[pos1].size();++i)
        {
            v[pos[b]].push_back(v[pos[a]][i]);
            v[pos1].erase(v[pos1].begin()+i);
            pos[v[pos[a]][i]]=pos[b];
            --i;
        }
    }
    return v;
}
vector<vector<int> > pile_over(vector<vector<int> > v,int a,int b)
{
    if(pos[a]!=pos[b])
    {
        int pos1=pos[a],pos2=pos[b];
        int i;
        for(i=0;v[pos1][i]!=a;++i);
        for(;i<v[pos1].size();++i)
        {
            v[pos2].push_back(v[pos1][i]);
            int tt=v[pos1][i];
            v[pos1].erase(v[pos1].begin()+i);
            pos[tt]=pos2;
            --i;
        }
    }
    return v;
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int> > v;
    for(int i=0;i<n;++i)
    {
        pos[i]=i;
        vector<int> temp;
        temp.push_back(i);
        v.push_back(temp);
    }
    while(1)
    {
        /*for(int i=0;i<v.size();++i)
            {
                cout << i << ":" << " ";
                for(int j=0;j<v[i].size();++j)
                {
                    cout << v[i][j] << " ";
                }
                cout << endl;
            }
        for(int i=0;i<v.size();++i) cout << pos[i] << " ";*/
        //cout << endl;
        string s;
        cin >> s;
        if(s=="quit")
        {
            for(int i=0;i<v.size();++i)
            {
                cout << i << ":" << " ";
                for(int j=0;j<v[i].size();++j)
                {
                    cout << v[i][j] << " ";
                }
                cout << endl;
            }
            break;
        }
        else
        {
            if(s=="move")
            {
                int a;
                cin >> a;
                cin >> s;
                if(s=="onto")
                {
                    int b;
                    cin >> b;
                    v=move_onto(v,a,b);
                }
                else if(s=="over")
                {
                    int b;
                    cin >> b;
                    v=move_over(v,a,b);
                }
                else
                {
                    break;
                }
            }
            else if(s=="pile")
            {
                int a;
                cin >> a;
                cin >> s;
                if(s=="onto")
                {
                    int b;
                    cin >> b;
                    v=pile_onto(v,a,b);
                }
                else if(s=="over")
                {
                    int b;
                    cin >> b;
                    v=pile_over(v,a,b);
                }
                else
                {
                    break;
                }
            }
            else
            {
                break;
            }
        }
    }
    return 0;
}

Help me too.
I try to many type of programming but receive only runtime error!

[aaa111]

Please Help, I am getting Time Limit each time i submit. I guess my program fell into infinite loop somewhere. Can anybody provide me some critical input.

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>

using namespace std;

#define TRUE  1
#define FALSE 0

typedef struct Node
{
	int    value;
	struct Node *Next;
	struct Node *Prev;
}Node;

typedef struct List
{ 
	Node  *Start;
	Node  *Head;
	Node  *Owner;
	Node  *Moved_To;
}List;

void Init_Data(List *list,int size);
void Init(List *list);
void Add_Node(List *list,int Data,int flag);
Node *Create_Node(void);
void Traverse_List(List *list);
void Move_Onto(List *list,int size,int num1,int num2);
void Move_Over(List *list,int size,int num1,int num2);
void Move_Block_Node(List *list,Node *node_a,Node *node_a_end,Node *node_b);
void Remove_Tops(List *list,Node *index,Node *Pos);
void Delete_List(List *list);
void MoveOnto(List *list,List *l1,Node *index,Node *node_a,Node *node_b);
void MoveOver(Node *a_index,Node *b_index,Node *node_a,Node *node_b);
void Pile_Onto(List *list,int size,int num1,int num2);
void PileOnto(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b);
void Pile_Over(List *list,int size,int num1,int num2);
void PileOver(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b);

int main(void)
{
	int n;
	int i = 0;
	int  cmd_a,cmd_b;
	int  number_1,number_2;
	string ca,cb;
	List *list = NULL;
	
	cin >> n;

	list = (List *)malloc(sizeof(List) * n);
	
	Init_Data(list,n);	
	
	for(i = 0 ; i < n; ++i)
	{
		printf("%d: ",i);	
		Traverse_List(&list[i]);
		printf("\n");
	}

	number_1 = number_2 = 0;	
	
	while(cin >> ca && ca != "quit")
	{
		cin >> number_1 >> cb >> number_2;

		cmd_a = (ca == "move")? 1 : 2;
		cmd_b = (cb == "onto")? 1 : 2;
		
		if(number_1 == number_2)
			cmd_a = 3;

		switch(cmd_a)
		{
			case 1:
				if(cmd_b == 1)
					Move_Onto(list,n,number_1,number_2);
				else
					Move_Over(list,n,number_1,number_2);
				break;
			case 2:
				if(cmd_b == 1)
					Pile_Onto(list,n,number_1,number_2);
				else
					Pile_Over(list,n,number_1,number_2);
				break;
			default:
				break;
		}

		for(i = 0 ; i < n; ++i)
		{
			printf("%d: ",i);	
			Traverse_List(&list[i]);
			printf("\n");
		}
	}

	for(i = 0 ; i < n; ++i)
		Delete_List(&list[i]);
	
	free(list);

	return 0;
}

void Init(List *list)
{		
	list->Head  = (Node *)malloc(sizeof(Node)*1);
	
	list->Start		  = list->Head;
	list->Head->Next  = list->Head;
	list->Head->Prev  = list->Head;	
	list->Moved_To    = list->Head;	
	list->Owner       = NULL;
	list->Head->value = 0;
}

void Init_Data(List *list,int size)
{
	int i;

	for(i = 0 ; i < size ; ++i)
	{
		Init(&list[i]);
		Add_Node(&list[i] , i  , TRUE);
	}
}

void Move_Onto(List *list,int size,int num1,int num2)
{
	int  i = 0;
	Node *node_a,*node_b;
	
	if(list[num1].Moved_To == list[num2].Moved_To)
		return;

	node_a = list[num1].Owner;
	node_b = list[num2].Owner;
	
	Remove_Tops(list,list[num1].Moved_To,node_a);
	Remove_Tops(list,list[num2].Moved_To,node_b);
	
	MoveOnto(&list[num2],&list[num1],list[num1].Moved_To,node_a,node_b);	

	list[num1].Moved_To = list[num2].Moved_To;
}

void MoveOnto(List *list,List *l1,Node *index,Node *node_a,Node *node_b)
{
	if(index->Next == node_a)
	{
		index->Prev = index;
		index->Next = index;
	}
	
	node_a->Prev->Next = node_a->Next; 
	
	node_a->Next = node_b->Next;
	node_a->Prev = node_b;
	node_b->Next = node_a;

	list->Moved_To->Prev = node_a;		
}


void Move_Over(List *list,int size,int num1,int num2)
{
	int  i = 0;
	Node *node_a,*node_b;
	
	if(list[num1].Moved_To == list[num2].Moved_To)
		return;

	node_a = list[num1].Owner;
	node_b = list[num2].Owner;

	Remove_Tops(list,list[num1].Moved_To,node_a);
	
	MoveOver(list[num1].Moved_To,list[num2].Moved_To,node_a,node_b);
	
	list[num1].Moved_To = list[num2].Moved_To;
}


void MoveOver(Node *a_index,Node *b_index,Node *node_a,Node *node_b)
{
	if(a_index->Next == node_a)
	{
		a_index->Prev = a_index;
		a_index->Next = a_index;
	}
	
	a_index->Prev = node_a->Prev;

	node_a->Prev->Next = node_a->Next; 
	
	b_index->Prev->Next = node_a;
	node_a->Next	    = b_index;
	node_a->Prev	    = b_index->Prev;
	b_index->Prev		= node_a; 
}

void Pile_Onto(List *list,int size,int num1,int num2)
{
	int  i = 0;
	Node *node,*node_a_start,*node_a_end,*node_b,*node_b_list;

	if(list[num1].Moved_To == list[num2].Moved_To)
		return;

	node_a_start = list[num1].Owner;
	node_a_end   = list[num1].Moved_To->Prev;
	
	node_b		 = list[num2].Owner;
	
	Remove_Tops(list,list[num2].Moved_To,node_b);
		
	PileOnto(&list[num2],list[num1].Moved_To,node_a_start,node_a_end,node_b);

	node = node_a_start;
	
	while(node != list[num2].Moved_To)
	{
		list[node->value].Moved_To = list[node_b->value].Head;	
		node = node->Next;
	}
}

void PileOnto(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b)
{
	if(index->Next == node_a_start)
	{
		index->Prev = index;
		index->Next = index;
	}
	else
	{
		index->Prev = node_a_start->Prev;
	}
	
	node_a_start->Prev->Next = node_a_end->Next; 
	
	node_a_end->Next   = node_b->Next;
	node_a_start->Prev = node_b;
	node_b->Next	   = node_a_start;

	list->Head->Prev   = node_a_end;		
}

void Pile_Over(List *list,int size,int num1,int num2)
{
	int  i = 0;
	Node *node,*node_a_start,*node_a_end,*node_b,*node_b_list;
	
	if(list[num1].Moved_To == list[num2].Moved_To)
			return;

	node_a_start = list[num1].Owner;
	node_a_end   = list[num1].Moved_To->Prev;
	
	node_b		 = list[num2].Moved_To->Prev;
	
	node = node_a_start;

	PileOver(&list[num2],list[num1].Moved_To,node_a_start,node_a_end,node_b);

	while(node != list[num2].Moved_To)
	{
		list[node->value].Moved_To = list[num2].Head;	
		node = node->Next;
	}
}

void PileOver(List *list,Node *index,Node *node_a_start,Node *node_a_end,Node *node_b)
{
	if(index->Next == node_a_start)
	{
		index->Prev = index;
		index->Next = index;
	}
	else
	{
		index->Prev = node_a_start->Prev;
	}
	
	node_a_start->Prev->Next = node_a_end->Next; 
	
	node_a_end->Next   = node_b->Next;
	node_a_start->Prev = node_b;
	node_b->Next	   = node_a_start;

	list->Head->Prev   = node_a_end;		
}

void Remove_Tops(List *list,Node *index,Node *Pos)
{
	Node *Curr = Pos->Next; 
	Node *Tmp;
		
	while(Curr != index)
	{
		Tmp = Curr->Next;

		list[Curr->value].Owner->Prev = list[Curr->value].Head;
		list[Curr->value].Owner->Next = list[Curr->value].Head;		
		list[Curr->value].Head->Next  = list[Curr->value].Owner;
		list[Curr->value].Head->Prev  = list[Curr->value].Owner;
		list[Curr->value].Moved_To    = list[Curr->value].Head;

		Curr = Tmp;		
	}
	
	Pos->Next = index;
	list[Pos->value].Moved_To->Prev = Pos;
}

void Delete_List(List *list)
{
	Node *Curr; 

	free(list->Owner);

	free(list->Head);

	list->Head = NULL;
}

Node *Create_Node(void)
{
	Node *node = (Node *)malloc(sizeof(Node)*1);

	node->Next = NULL;
	node->Prev = NULL;

	return node;
}

void Add_Node(List *list,int Data,int flag)
{
	Node *node = Create_Node();
	
	Node *Head  = list->Head;
	node->value = Data;
	
	node->Prev       = Head->Prev;
	node->Next       = Head;
	Head->Prev->Next = node;
	Head->Prev		 = node;
	
	if(flag)
		list->Owner      = node;
}

void Traverse_List(List *list)
{
	Node *Curr;

	if(list->Head->Prev == list->Head || list->Head->Next == list->Head)
	{
		return;
	}

	Curr = list->Head->Next;

	while(Curr != list->Head)
	{
		printf("%d",Curr->value);
		Curr = Curr->Next;
		if(Curr != list->Head)
			printf(" ");
	}	
}

[mainul07]

Your program can not get any input....modify it than it will work and Runtime error will overcome

[IvanLH]

Hello, i've tried the problem 101 and i get a runtime error even thought when i run my program with commands directly written in the console, and reading form an input file it doesn't shows any exceptions, so here's my code, is in java 6.
import java.util.*;

public class Main{
public static void main(String args[]){
//Declaración de variables, arrays y stacks
Scanner in = new Scanner (System.in);
int numero = in.nextInt();//Lector de numero de cajas.
int op1 = 0;
int op2 = 0;
int d1 = 0;
int d2 = 0;
String c1 = "";
String c2 = "";
Stack[] pos = new Stack[numero];//Array de almacenamiento de los objetos "caja" en forma de stacks
int[] posact = new int[numero];//Array de posicion de cada caja
int bandera = 0;

for(int i = 0; i < posact.length; i++)//Inicialización de las posición de las cajas
posact = i;

for(int i = 0; i < pos.length; i++){//Creación de los stacks de cada columna
pos= new Stack();
pos.push(i);
}

String entr = in.nextLine();//Lector de comandos.

if (entr.equals("quit"))
bandera = 1;

while (bandera != 1){
StringTokenizer t = new StringTokenizer(entr);
try{
c1 = t.nextToken();
d1 = Integer.parseInt(t.nextToken());
c2 = t.nextToken();
d2 = Integer.parseInt(t.nextToken());
}
catch(NoSuchElementException e){}
if (c1.equals("move"))
op1 = 1;

if (c1.equals("pile"))
op1 = 2;

if (c2.equals("onto"))
op2 = 1;

if (c2.equals("over"))
op2 = 2;

if (d1 != d2 && pos[d1] != pos[d2])
operador(pos, posact, op1, op2, d1, d2);

entr = in.nextLine();

if (entr.equals("quit"))
bandera = 1;
}
Stack[] pos2 = new Stack[pos.length];

for ( int i = 0;i < pos2.length; i++){
pos2 = new Stack();

while(!pos.empty()){
int a = Integer.parseInt((pos.pop()).toString());
pos2.push(a);}}

for (int i = 0; i < pos2.length; i++){
System.out.print(i + ": ");

while(pos2.empty() == false){
System.out.print(pos2.pop());
System.out.print(" ");}

System.out.println();}
}//Fin del método main.


public static void operador (Stack[] ma, int[] pos, int oper1, int oper2 , int num1, int num2 ){
if (oper1 == 1 && oper2 == 1){

String a = (ma[pos[num1]].peek()).toString();
String b = (ma[pos[num2]].peek()).toString();
int numt1 = Integer.parseInt(a);
int numt2 = Integer.parseInt(b);

while (numt1 != num1){
int nump1 = Integer.parseInt((ma[pos[num1]].pop()).toString());
ma[numt1].push(nump1);
pos[nump1] = nump1;
numt1 = Integer.parseInt((ma[pos[num1]].peek()).toString());
}

while (numt2 != num2){
int nump2 = Integer.parseInt((ma[pos[num2]].pop()).toString());
ma[numt2].push(nump2);
pos[nump2] = nump2;
numt2 = Integer.parseInt((ma[pos[num2]].peek()).toString());
}

ma[pos[num2]].push(Integer.parseInt((ma[pos[num1]].pop()).toString()));
pos[num1] = pos[num2];
}
if (oper1 == 1 && oper2 == 2){

String a = (ma[pos[num1]].peek()).toString();
int numt1 = Integer.parseInt(a);

while (numt1 != num1){
int nump1 = Integer.parseInt((ma[pos[num1]].pop()).toString());
ma[numt1].push(nump1);
pos[nump1] = nump1;
numt1 = Integer.parseInt((ma[pos[num1]].peek()).toString());
}
ma[pos[num2]].push(Integer.parseInt((ma[pos[num1]].pop()).toString()));
pos[num1] = pos[num2];


}
if(oper1 == 2 && oper2 == 1){


String b = (ma[pos[num2]].peek()).toString();
int numt2 = Integer.parseInt(b);

while (numt2 != num2){
int nump2 = Integer.parseInt((ma[pos[num2]].pop()).toString());
ma[numt2].push(nump2);
pos[nump2] = nump2;
numt2 = Integer.parseInt((ma[pos[num2]].peek()).toString());
}
int bandera = 0;
Stack[] temp = new Stack[ma.length];
temp[1] = new Stack();

while(bandera != 1){
if (ma[pos[num1]].peek().equals(num1))
bandera = 1;
int rec = Integer.parseInt((ma[pos[num1]].pop()).toString());
pos[rec] = pos[num2];
temp[1].push(rec);}


while(!temp[1].empty())
ma[pos[num2]].push(temp[1].pop());
}
if (oper1 == 2 && oper2 == 2){
int bandera = 0;
Stack[] temp = new Stack[ma.length];
temp[1] = new Stack();

while(bandera != 1){

if (ma[pos[num1]].peek().equals(num1))
bandera = 1;
int rec = Integer.parseInt((ma[pos[num1]].pop()).toString());
pos[rec] = pos[num2];
temp[1].push(rec);}

while(!temp[1].empty())
ma[pos[num2]].push(temp[1].pop());}
}//Fin del método operadores.
}//Fin de la clase.

[brianfry713]

Don't put any trailing spaces on a line