Deadlocks e matrizes!

[WolfmanZ]

Boas tenho um problema para verificar se há deadlock ou não!

tenho duas matrizes que serao preenchida com "0" isto é relaçao chef tem ingrediente :

I1 I2 I3 I4 I5

C1 1 1 0 0 0

C2 0 0 1 0 0

C3 0 0 0 0 1

outra relaçao chef quer ingrediente:

I1 I2 I3 I4 I5

C1 0 0 0 0 1

C2 0 0 0 0 1

C3 0 0 0 0 1

Neste caso nao há deadlock! Como faço para ver se há ou nao deadlock???

Obrigado desde já!!

[brunoais]

Não percebi.

[HappyHippyHippo]

o que implica deadlock neste caso ???

[WolfmanZ]

O enunciado é este :

Input

The input consists of (1+ 2.N) lines, with the limits 1≤N, K 30.

The first line contains two integers specifying the number of chefs (N) (1,2. … N) and number of ingredients (K) – (1,2, .. K)

The next N lines describe for each chef the ingredients that he currently has. Each line contains an integer (the total number of ingredients he has) followed by the numbers of the ingredients he actually has.

The next N lines describe for each chef the ingredients that he wants but doesn’t currently have. Each line contains an integer (the total number of ingredients he wants) followed by the numbers of ingredients he wants.

Output

The output is either the string “Happy Restaurant” or “Deadlock and Chaos”

Sample Input

3 5 // numero de chefs e ingredientes

2 1 2 // chef 1 tem 2 ingredientes o nº1 e nº2

1 3 // chef 2 tem 1 ingredientes o nº3

1 5 // chef 3 tem 1 ingredientes o nº5

1 5 // chef 1 quer 1 ingredientes o nº5

1 4 // chef 2 quer 1 ingredientes o nº4

1 3 // chef 3 quer 1 ingredientes o nº3

Sample Output

Happy Restaurant

Sample Input

3 5 // numero de chefs e ingredientes

2 1 2 // chef 1 tem 2 ingredientes o nº1 e nº2

1 3 // chef 2 tem 1 ingredientes o nº3

1 5 // chef 3 tem 1 ingredientes o nº5

1 5 //chef 1 quer 1 ingrediente 5

1 4 // chef 2 quer 1 ingrediente 4

2 3 2 // chef 3 quer 2 ingredientes 3 e 2

Sample Output

Deadlock and Chaos

[HappyHippyHippo]

ok ... o uso de deadlock é muito rebuscado, isto porque essa palavra quer dizer outra coisa para quem programa. Implica que o programa/algoritmo chega a um ponto que impossibilita a continuação, fica bloqueado.

no entanto o enunciado continua a ser muito escasso ...

continua a não dizer o que leva a um deadlock ...

eu olho para os exemplos e pergunto-me ... o raio do chefe 2 quer sempre o ingrediente 4 e ninguém tem ... isso não deveria dar o dito deadlock ???

porque leva no segundo caso, só porque o chefe quer mais o ingrediente 2, isso leva ao dito deadlock ???? o ingrediente existe e mais ninguém o quer !!!!

[WolfmanZ]

tipo imagina, há 5 ingredientes nos exemplos ninguém tem o 4º ingrediente esta na prateleira (XD ex:sal);

http://imageshack.us...ockexemplo.png/ nao consegui meter a imagem

Edited May 27, 2012 at 12:29 AM by WolfmanZ

[HappyHippyHippo]

continuas a não dizer o que implica acontecer para levar a um deadlock !!!!! sem essa informação é impossível te ajudar !!!

[WolfmanZ]

O que leva ao deadlock é que na imagem/exemplo que te dei á um ciclo fechado entre C1-ingrediente 5-C3-Ingrediente 2 - C1 como á este ciclo há deadlock. Por ser assim é que nao estou a ver como verificar a existencia ou na desse ciclo e consequentemente deadlock!

[HappyHippyHippo]

a razão de existência de deadlock é ... bem ... não vou dizer porque não há necessidade ( porque sinceramente NÃO TEM SENTIDO )

a maneira de como saber que num (di)grafo existem ciclos é fazer a pesquisa por profundidade marcando os nós visitados. quando um nó é revisitado, existe um ciclo

[WolfmanZ]

a maneira de como saber que num (di)grafo existem ciclos é fazer a pesquisa por profundidade marcando os nós visitados. quando um nó é revisitado, existe um ciclo

sim é isso que quero mas como faço isso com matrizes ou tenho que transformar as matrizes em grafos?

[HappyHippyHippo]

não propriamente ... simplesmente consideras os 1's como arestas do nó C(x) para o nó I(x)

[WolfmanZ]

pois e como faço isso em codigo ?