|
VIP user
Регистрация: 10.03.2011
Сообщений: 765
Сказал(а) спасибо: 10
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 3453
|
Коммивояжер
Цитата:
##include <iostream>
using namespace std;
const int inf=1E9,NMAX=16;
int n,i,j,k,m,temp,ans,d[NMAX][NMAX],t[1<<NMAX][NMAX];
bool get(int nmb,int x)
{ return (x&(1<<nmb))!=0; }
int main()
{
cin >>n;
for (i=0;i<n;++i)
for (j=0;j<n;++j) cin>>d[i][j];
t[1][0]=0; m=1<<n;
for (i=1;i<m;i+=2)
for (j=(i==1)?1:0;j<n;++j)
{
t[i][j]=inf;
if (j>0 && get(j,i))
{
temp=i^(1<<j);
for (k=0;k<n;++k)
if (get(k,i) && d[k][j]>0) t[i][j]=min(t[i][j],t[temp][k]+d[k][j]);
}
}
for (j=1,ans=inf;j<n;++j)
if (d[j][0]>0) ans=min(ans,t[m-1][j]+d[j][0]);
if (ans==inf) cout<<-1; else cout<<ans;
}
|
Задача о 8 ферзях
Цитата:
void main()
{
#include <stdlib.h>
#include <gtk/gtk.h>
#include <gdk/gdkkeysyms.h>
#include <../cairo/cairo.h>
/*Размеры окна */
#define WIDTH 720
#define HEIGHT 700
/*Количество ферзей*/
#define N 8
// ->> Обьявление функций
gboolean Draw ( GtkWidget*, GdkEventExpose*, gpointer );
gboolean KeyPress ( GtkWidget*, GdkEventKey*, gpointer );
char check ( int* , int );
void print_field ( int* , int );
void build ( int* , int );
// <<-
// ->> Указатели для хранения виджета(окна) и 2 изображений (доски и ферзя)
GtkWidget *window = NULL;
cairo_surface_t *background = NULL;
cairo_surface_t *queen = NULL;
// <<-
// ->> Максимальное количество вариантов и текущий просматриваемый вариант расстановки
int MaxNumber = 0;
int CurrentVariant = 0;
// <<-
// ->> Двумерный массив хранения координат по X для каждого из 92 случаев для 8 ферзей и строка вывода собщения
int AllPos[93][8];
char MessageString[100 + 1];
// <<-
// ->> Просмотр шахматной доски и проверка, не находится ли поле под боем
char check ( int *A, int n )
{
int i,j;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
if ( ( A[i] == A[j] ) && ( i != j ) && ( A[i] != 0 ) )
return 0;
if ( ( ( A[i] + i ) == ( A[j] + j ) ) && ( i != j ) && ( A[i] != 0 ) && ( A[j] != 0 ) )
return 0;
if ( ( ( A[i] - i ) == ( A[j] - j ) ) && ( i != j ) && ( A[i] != 0 ) && ( A[j] != 0 ) )
return 0;
}
return 1;
}
void print_field ( int *A, int n )
{
int i,j;
for (i = 0; i < n; i++)
{
for( j = 0; j < n; j++)
printf("--");
printf("-\n");
for (j = 1; j < A[i]; j++)
printf("| ");
printf("|F");
//Записываем расположениt ферзя по X координате
AllPos[MaxNumber][i] = A[i];
for (j = A[i]; j < n; j++)
printf("| ");
printf("|\n");
}
for(j = 0; j < n; j++)
printf("--");
printf("-\n\n");
//Увеличиваем кол-во вариантов
MaxNumber++;
}
void build ( int *A, int n )
{
int *B;
int i,k;
for( k = 0; ( A[k] != 0 ) && ( k < n ); k++ );
if( k >= n )
{
print_field ( A, n );
return;
}
B = (int *) malloc( n * sizeof(int) );
for ( i = 0; i < k; i++ )
B[i] = A[i];
for ( i = k; i < n; i++ )
B[i] = 0;
for ( i = 1; i <= n; i++ )
{
B[k] = i;
if ( check ( B, n ) )
build ( B, n );
}
free( B );
}
int main ( int argc, char *argv[] )
{
gtk_init (&argc, &argv); //Инициализируем GTK+
window = gtk_window_new (GTK_WINDOW_TOPLEVEL); //Создаём окно поверх остальных созданных
gtk_window_set_title (GTK_WINDOW (window), "Queen Algorithm"); //Устанавливаем заголовок окна
background = cairo_image_surface_create_from_png ( "image/bg.png" ); //Открываем изображение доски
queen = cairo_image_surface_create_from_png ( "image/queen.png" ); //Открываем изображение ферзя
gtk_widget_set_size_request ( window, WIDTH, HEIGHT ); //Устанавливаем размеры окна
gtk_window_set_resizable ( GTK_WINDOW ( window ), FALSE ); //Запрещаем возможность растяжения окна
gtk_window_set_position ( GTK_WINDOW ( window ), GTK_WIN_POS_CENTER ); //Устанавливаем окно по-середине экрана
gtk_widget_realize ( window );
/*
->> Создаём 3 события: 1 - проверяет закрыто ли окно, в случае закрытия вызывает функцию остановки главного цикла GTK
2 - События прорисовки экрана, требуется для прорисовки изображения
3 - Событие, отслеживающее нажатие клавиши
*/
g_signal_connect ( window, "destroy", gtk_main_quit, NULL );
g_signal_connect ( window, "expose-event", Draw, NULL );
g_signal_connect ( window, "key_press_event", KeyPress, NULL );
// <<-
gtk_widget_show_all ( window ); //Отображаем наше окно
//построение
int A[N];
int i;
for ( i = 0; i < N; i++)
A[i] = 0;
build(A, N);
char str[] = "Resheniy: %i ";
printf(str, MaxNumber);
// <<-
gtk_main (); //Запускаем главный, бесконечный цикл GTK
/* ->>
После срабатывания события закрытия окна, выключается главный цикл, после чего мы уничтожаем
в оперативной памяти изображения, которые были открыты ранее (Доска и ферзь)
*/
cairo_surface_destroy ( background );
cairo_surface_destroy ( queen );
// <<-
return 0;
}
// ->> Функция вызывается после срабатывания события нажатия клавиши
// ->> Параметры: 1 - виджет, в котором сработало событие - т.е. наше окно
// ->> 2 - Параметры самого события
// ->> 3 - Данные, передаваемые в функцию, но здесь они в принципе не нужны, т.к. мы ничего не передаём
gboolean KeyPress ( GtkWidget *wid, GdkEventKey *event, gpointer data )
{
//Проверка, какая клавиша была нажата..
switch( event->keyval )
{
//Если клавиша в право или D - показать след. вариант расстновки
case GDK_Right:
case GDK_d:
printf("Right is pressed\n");
//Проверка, что если мы дошли до конца списка возможных вариантов расстановки - то начать заного
if( ++CurrentVariant >= MaxNumber )
CurrentVariant = 0;
//Стереть текущее расположение изображение в окне
gtk_widget_queue_clear(wid);
break;
//Если влево или A - предыдущий
case GDK_Left:
case GDK_a:
printf("Left is pressed\n");
//Тут аналогично
if( --CurrentVariant < 0 )
CurrentVariant = MaxNumber - 1;
//Стереть текущее расположение изображение в окне
gtk_widget_queue_clear(wid);
break;
}
return TRUE;
}
//Функция вызывается при прорисовке изображений внутри окна, параметры те же, что и в предыдущей функции
gboolean Draw ( GtkWidget *wid, GdkEventExpose *event, gpointer data )
{
cairo_t *cr ;
//Создаём область для рисования в окне
cr = gdk_cairo_create ( wid->window );
//Рисуем изображение шахматной доски в координатах (0.0)
cairo_set_source_surface ( cr, background, 0, 0 );
//Рисуем...
cairo_paint ( cr );
//Циклом прогоняем все 8 ферзей, и каждый рисуем в соответствии с координатами умноженными на масштаб, т.к. область рисования у нас не единичная
int i;
for(i = 0; i < N; i++) {
cairo_set_source_surface ( cr, queen, 90 * AllPos[CurrentVariant][i] - 90 + 3, i * 90 + 4 );
cairo_paint ( cr );
}
//Формируем строку вывода вариантов
sprintf(MessageString, "Current Variant: %d, Max: %d", CurrentVariant + 1, MaxNumber);
//Устанавливаем цвет текста, его размер, и месторасположение
cairo_set_source_rgb(cr, 1.0, 0.8, 0.2);
cairo_set_font_size(cr, 20);
cairo_move_to(cr, 10, HEIGHT - 10);
//Выводим текст
cairo_show_text(cr, MessageString);
//Удаляем область рисования
cairo_destroy ( cr );
return TRUE;
}
}
|
p.s. Не откажусь от webmoney любой суммы, или денежки на телефон=)
|