Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Java программирование > Общие вопросы по Java, Java SE, Kotlin
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 25.08.2016, 13:50   #1
kostan33
Пользователь
 
Регистрация: 25.08.2016
Сообщений: 10
По умолчанию Комбинаторика. Задача Ферзь II

Решаю эту задачу
ТИМУС 1425
По сути доску представляю доску в виде массива
и работаю с массивом вот код
Код:
import java.util.*;
import java.util.regex.*;
import java.awt.Point;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;

public class P425 {
    static int N;
    static int S;
    static HashSet<Long> set = new HashSet<Long>();
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        S = in.nextInt();
        if(N==1 && S==2) { System.out.println(1); return; }
        if(N <= 2) { System.out.println((long)pow(S,N)); return; }
        int[] C = new int[N];
        long pos = 0;
        for(int i=0; i<N; i++) {
            pos = pos*100+in.nextInt()-1;
        }
        bfs(pos);
        HashSet<Long> W = new HashSet<Long>(set);
        set.clear();
        for(Long L:W)
            bfs(L);
        System.out.println(set.size());
    }
    public static void bfs(long pos) {
       int[] C = toC(pos);
       for(int i=0; i<N; i++)
           for(int j=0; j<S; j++) {
               if(j==C[i]) continue;
               int tmp = C[i];
               C[i] = j;
               set.add(toL(C));
               C[i] = tmp;
           }

       for(int a=0; a<pow(2,N); a++) {
    OUTER: for(int j=1; j<S; j++) {
                int[] X = new int[N];
                for(int k=0; k<N; k++) {
                    int f = ((a>>k)&1) == 1 ? 1 : -1;
                    X[k] = C[k]+f*j;
                    if(X[k] >= S || X[k]<0) continue OUTER;
                }
                set.add(toL(X));
            }
       }
    }
    
    public static long toL(int[] C) {
        long ans = 0;
        for(int i=0; i<N; i++)
            ans = ans*100+C[i];
        return ans;
    }
    public static int[] toC(long L) {
        int[] C = new int[N];
        for(int i=N-1; i>=0; i--) {
            C[i] = (int)(L%100);
            L/=100;
        }
        return C;
    }
}
но к сожалению получаю Memory limit exceeded 16
у кого есть идеи как получить АС?
Попытки

Последний раз редактировалось Аватар; 25.08.2016 в 15:02.
kostan33 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Здравствуйте! С++ TinaD Фриланс 10 08.09.2012 08:13
Здравствуйте! extremalka Помощь студентам 1 23.04.2012 23:53
Здравствуйте! sandraq Операционные системы общие вопросы 2 31.10.2009 18:46