Buenas, ya he vuelto

Pues al final me he metido con el de grafos, me ha gustado mucho xD Y por cierto, decirte que me falto implementarle lo de varios casos por falta de tiempo, es decir, la entrada al programa es identica, solo que obvia el numero de casos y solo te resolvera el primero, si quieres probar otros casos hay que ejecutar de nuevo el programa (sorry, obviamente no presentaria eso asi en un concurso xDD)

Pero nada, queria que simplemente le echaras un vistazo a la parte principal del programa, el algoritmo y tal que es lo que importa al fin y al cabo, y ver que cambiarias tu o como lo harias (seguro que se puede hacer mas eficientemente que el mio )

Aqui te lo dejo (Otra cosa, solo lo he hecho en pascal, en cuanto vuelva a tener un rato disponible intentare pasarlo a C a ver):

program circulos;
 
const
	MAX = 20;
 
type
	TValores  = Record
		                Asignado : boolean; 
				Color       : boolean; { 'True' = Verde; 'False' = Amarillo }
			End;
	TVertices = array [0..MAX] of TValores;
	TCasos = array [1..MAX] of TVertices;
 
var
	nCasos 	: integer;
	nVertices 	: integer;
	nAristas	: integer;
	inicio, fin  : integer;
	vertices 	: TVertices;
	casos	: TCasos;
	flag		: boolean;
	i		: integer;
 
procedure init_vertices (var c : TCasos);
 
var 
	i, j : integer;
 
begin
 
	for i := 1 to MAX do
		for j := 0 to MAX do
		begin
			c[i][j].Asignado := false;
			c[i][j].Color := false;
		end;
 
end;
 
function evalua (var v : TVertices; inicio, fin : integer) : boolean;
 
begin
 
	if (v[inicio].Asignado = false) and (v[fin].Asignado = false) then { si ninguno ha sido asignado aun }
	begin
		v[inicio].Asignado := true;
		v[inicio].Color := true;
		v[fin].Asignado := true;
		v[fin].Color := false;
		evalua := true;
	end
	else
	begin
		if (v[inicio].Asignado) xor (v[fin].Asignado) then { si uno de los dos esta asignado }
		begin
			if v[fin].Asignado = false then 
			begin
				v[fin].Asignado := true; { lo marcamos como coloreado }
				v[fin].Color := not v[inicio].Color; { y le ponemos el color contrario al del otro vertice }
			end
			else
			begin  { en caso de que el que no estuviese coloreado aun fuera el vertice inicial, lo mismo para este }
				v[inicio].Asignado := true; 
				v[inicio].Color := not v[fin].Color;
			end;
			evalua := true;
		end
		else
		begin  { si entramos aqui es porque ambos ya estan coloreados, comprobemos si es incompatible }
			if v[inicio].Color = v[fin].Color then
				evalua := false
			else
				evalua := true;
		end;
	end;
 
end;
 
{ -- MAIN --}
 
begin  
 
	init_vertices (casos);
	flag := true;
	readln (nCasos);
	readln (nVertices, nAristas);
	for i := 1 to nAristas do
	begin
		readln (inicio, fin);
		flag := flag and (evalua (vertices, inicio, fin));
	end;
	if flag then
		writeln ('Miguel, a pintar')
	else
		writeln ('No pierdas el tiempo');
 
end.

Ale, ahi lo tienes, dispara

Decirte tambien que voy a estar fuera hasta el viernes o asi, en cuanto vuelva a estar online le meto mano al susodicho problema nº 2, y tal vez traducir este a C

Gracias de nuevo por tus problemas, de verdad que son muy interesantes y me he entretenido mucho con ellos, sobre todo el ultimo claro (pa haber salido de un examen de GRAFOS hoy mismo y ponerme a hacer problemas de GRAFOS... xDD hay que echarle ganas)

Saludos!

Pues ante la ausencia de respuestas, aclaro como se hace el de las minas. Recursivamente sería empezar en cada una de las casillas de la primera fila e ir probando cada camino desde ahí. Esto es terriblemente lento además de que probamos más de una vez el mismo camino. La solución es por DP.

Creamos una matriz de carácteres para guardar el mapa y otra del mismo tamaño para almacenar números. Entonces simplemente hay que recorrer dicha matriz: si en la posición hay una mina el número lo ponemos a un máximo declarado antes, de lo contrario será el mínimo entre el de arriba y las dos diagonales de arriba + 1. No hace falta decir que la primera fila ha de valer cero en todas las casillas excepto las que tengan minas. La solución final es el mínimo de todas las posiciones de la última fila.

No pondré más problemas, puesto que no tengo demasiado tiempo y casi nadie se pasa por aquí a resolverlos

Un saludo de ghastlyX

 ahm... que se me hace que se resuelve con una matriz de adyacencia deja un rato libre que no se queda sin solución

en realidad se me ocurrió warshall pero apenas lo entiendo y en 6 horas tengo un control de lectura!

Ya que estamos. Me tome el trabajo de pasar el algortimo a Java 

import java.io.*;
import java.util.Random;
public class minas {
    public static void main() throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        char[][] caracteres;
        int [][] resultado;
        System.out.print("Ingrese cantidad de filas:");
        int filas=Integer.parseInt(br.readLine());
        System.out.print("Ingrese cantidad de columnas:");
        int columnas=Integer.parseInt(br.readLine());
        caracteres=new char[filas][columnas];
        resultado=new int[filas][columnas];
        Random rnd=new Random();
        for (int i=0; i<filas; i++)
        {
            for(int j=0;j<columnas;j++)
            {
                //genero la tabla/////////////
                int aleat=rnd.nextInt(2);
                if (aleat==1)
                    caracteres[i][j]='M';
                    else caracteres[i][j]='L';
                //////////////////////////////
                //
                if (caracteres[i][j]=='M')
                    resultado[i][j]=99;
                else //si esta libre
                {
                    if (i==0) //si es la primera fila
                        resultado[i][j]=0;
                    else //en cualquier otro caso
                    {
                        if ((j>0)&&(j<columnas-1))
                            resultado[i][j]=min(resultado[i-1][j-1]+1,resultado[i-1][j],resultado[i-1][j+1]+1);
                        else if (j==0)
                            resultado[i][j]=min(resultado[i-1][j],resultado[i-1][j+1]+1,99);
                             else
                               resultado[i][j]=min(resultado[i-1][j],resultado[i-1][j-1]+1,99);
                            }           
                        }       
            }
        }
        int menor=99;
        for (int j=0; j<columnas;j++)
            if (resultado[filas-1][j]<menor)
                menor=resultado[filas-1][j];
        if (menor==99)
            System.out.println("Yum Yum");
            else System.out.println(menor);
}
    public static int min(int num1, int num2, int num3){
        int menor=num1;
        if (num2<num1)
            menor=num2;
        if (num3<menor)
            menor=num3;
        return menor;
    }
}