ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1325. Грязь

AC.an interesting problem......
Послано Yu YuanMing 16 окт 2004 20:59
I manage to solve it in two way:

1.Use two bfs,one forward for change boot(see the adjacent same square as one region)...the other backward for the distance(based on step one,I think it has a bit like DP),and then you can solve it in O(nm).

2.Use dijkstra+heap.Just minimal heap can perform O(vlgv) in this problem(v=nm).Although it is a bit slow than 1,I think it is more simpler......

The interesting place is: In both of the two program(pascal),I only use
  one array[1..500,1..500]of byte,
  three array[1..500,1..500]of longint
it is 3250k,so the total memory won't more than 4000K.but the judge said P1 uses 5513K,P2 uses 4545K.Why will happen this thing?