Задача 5 (Хитрая мышь)

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции.
Руководители: к.ф-м.н., профессор Пирогов Владислав Юрьевич, ник - Vladislav_133; к.п.н, доцент Слинкин Дмитрий Анатольевич, ник - xdsl

Задача 5 (Хитрая мышь)

Сообщение Vladislav_133 04 апр 2015, 10:26

Здесь будет обсуждение
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача 5 (Хитрая мышь)

Сообщение hardcore_test 05 апр 2015, 01:10

Данную задачу решал с рекурсией. На каждом шаге проверял, есть ли клетка куда я могу пойти и где я еще не был, если есть, то иду в нее и запоминаю, что в эту клетку ходить нельзя и снова повторяю все действия. Если ходить не куда, то смотрю нахожусь ли я в начальной клетке и прошел ли я все клетки( определить это можно создав отдельный счетчик или просто пересчитать все пройденные клетки). Если действительно нахожусь в 1 клетке и прошел все клетки, то к счетчику ходов добавляю +1
Теперь ближе к коду.
Массив размером n*n логического типа будет хранить информацию о пройденных клетках true мы были в этой клетке, false не были. Методу передается значения: массива с ходами, клетки в которой мы находимся, размер поля, количество совершенных ходов
Код: Выделить всё
// задача №5 "Хитрая мышь"
// Быков Владислав Андреевич
// email - i596655@yandex.ru

import java.util.Scanner;

public class mouse {
   int sum = 0; // счетчик ходов

   public static void main(String[] args) {
      new mouse();
   }

   public mouse() {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      sc.close();
      if (n % 2 == 0) {
         boolean m[][] = new boolean[n][n];
         xod(m, 0, 0, n, 0);
         System.out.println(sum);
      } else
         System.out.println(0);
   }

   void xod(boolean m[][], int i, int j, int n, int k) {
      boolean f = true; // f отвечает за информацию о том был ход или нет,
                     // можно было бы из без нее, через else, но нет
      if ((i + 1 < n) && (m[i + 1][j] == false)) { //если сверху не стена и мы там еще не были то идем туда
         boolean m1[][] = new boolean[n][n]; // создаем новый массив
         for (int r = 0; r < n; r++)         // в него переносим значение из старого
            for (int t = 0; t < n; t++)
               m1[r][t] = m[r][t];
         m1[i + 1][j] = true;            //запоминаем, клетку в которую пойдем
         f = false;
         int k1 = k + 1;                  //увеличиваем количество пройденых ходов
         xod(m1, i + 1, j, n, k1);         // снова вызываем метод
      }
      if ((j + 1 < n) && (m[i][j + 1] == false)) { // идем вправо
         boolean m1[][] = new boolean[n][n];
         for (int r = 0; r < n; r++)
            for (int t = 0; t < n; t++)
               m1[r][t] = m[r][t];
         m1[i][j + 1] = true;
         f = false;
         int k1 = k + 1;
         xod(m1, i, j + 1, n, k1);
      }
      if ((i - 1 >= 0) && (m[i - 1][j] == false)) { // идем вниз
         boolean m1[][] = new boolean[n][n];
         for (int r = 0; r < n; r++)
            for (int t = 0; t < n; t++)
               m1[r][t] = m[r][t];
         m1[i - 1][j] = true;
         f = false;
         int k1 = k + 1;
         xod(m1, i - 1, j, n, k1);
      }
      if ((j - 1 >= 0) && (m[i][j - 1] == false)) { // идем влево
         boolean m1[][] = new boolean[n][n];
         for (int r = 0; r < n; r++)
            for (int t = 0; t < n; t++)
               m1[r][t] = m[r][t];
         m1[i][j - 1] = true;
         f = false;
         int k1 = k + 1;
         xod(m1, i, j - 1, n, k1);
      }
      if ((f) && (k == n * n) && (i == 0) && (j == 0))  // количество клеток n*n, начальные клетки 0 0
         sum++;

   }

}

С подцветкой синтаксиса по ссылке тык
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

Re: Задача 5 (Хитрая мышь)

Сообщение Vladislav_133 06 апр 2015, 20:54

Данная задача представляет собой классическую задачу на графе.
Алгоритм жадный, т.е. количество траекторий растет с огромной скорость.
По сути программы удовлетворительно работают для значений n от 2 до 7.
Кроме это можно увидеть закономерность: если n не четно, то мышь не сможет
обойти все комнаты.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача 5 (Хитрая мышь)

Сообщение Vladislav_133 06 апр 2015, 20:55

Сама программа

Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка cpp
#include <stdio.h>
#include <string.h>
#include <math.h>
//--------------------------------------
int rec(int, int, int);
//--------------------------------------
int n,m,i,j,s,pp,q,nn;
int mas[11][11];
//======================================
int main(){
    int p = scanf("%d",&n);
    if(p==EOF||n>7||n<2){
        printf("Error\n");
        return 0;
    }
    if(n==3||n==5||n==7){
        printf("0\n");
        return 0;
    }
    nn=n*n;
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            mas[i][j]=1;
    s=0; m=0;pp=0;q=0;
    rec(1,0,1);
    if(pp==1)
    printf("%d\n",2*s);
    else
    printf("0\n");
    return 0;
}
//=======================================
int rec(int x, int y, int m){
    if(x==n||y==n||x<0||y<0)    return 0;
    if(mas[x][y]==0)return 0;    
    if(x==0&&y==0&&m<nn&&q!=0)  return 0;
    q=1;
    mas[x][y]=0;
    if(m==nn){
        s++; pp=1; goto ex;
    }
    rec(x+1,y,m+1);
    rec(x-1,y,m+1);
    rec(x,y+1,m+1);
    rec(x,y-1,m+1);    
ex:    
    mas[x][y]=1;
    return 0;
}

 
Последний раз редактировалось Vladislav_133 06 апр 2015, 21:21, всего редактировалось 1 раз.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача 5 (Хитрая мышь)

Сообщение Vladislav_133 06 апр 2015, 21:19

Напрашиваются две возможности оптимизировать программу:

1. В самом начале мышь может выбрать два пути. Но каждый из этих путей даст одинаковое количество симметричных траекторий обхода. Следовательно можно выбрать в начале один путь, а затем умножить полученный результат на 2. Что, собственно, в программе у меня имеется.
2. Отсекать группы траекторий, которые заведомо не дадут нужного результата. Скажем, если первый шаг это x=0, y=1, то если мышь оказалась в точке x=1, y=0, а количество сделанных шагов <n-1, то дальше эта траектория отсекается. Я это не реализовал, а кто-нибудь это сделал?
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.


Вернуться в Олимпиада по программированию

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0