|
Java форум JavaTalks
форум программистов
|
|
|
|
| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
Петр : 707
Постоянный посетитель
Откуда: Москва
|
 Дек 17, 2011 12:47 |
 |
|
| PolarHare писал(а): |
| А разницы между есть/нету диагоналей? Это же просто поиск в ширину/покраска компонент связности. Ну разве что меньше массивы возможных ходов в два раза, но сам код не меняется. (ну или в два раза меньше копипаста, если массивы dx dy уже не модно) |
прошу решение тогда если опять так все просто )). |
|
|
|
 |
PolarHare : 182
Новичок
Откуда: Saint-Petersburg, Russia
|
| Дек 17, 2011 13:16 |
| |
|
Решение: (скорее всего не самое оптимальное, но близкое к нему)
Пусть есть у нас массив a двумерный из 1 и 0ей.
Создадим дополнительный массив col, говорящий о том, в какой цвет мы покрасили число из исходного массива.(исходно везде 0-т.е. еще не покрасили) Единички из одного мн-ва будут покрашены в один цвет.
теперь примерный код решения:
| Код: |
col = 1; // первый цвет
по всем x от 1 до n:
по всем y от 1 до n:
если a[x][y] == 1 и col[x][y] == 0 //если еще не покрасили единичку
col(col, x, y);//то покрасим ее + покрасим все соседние
col++; // увеличили номер цвета
|
col(col, x, y):
| Код: |
col[x][y] = col;
dx = {0, 1, 1, 1, 0, -1, -1, -1};//пути по часовой стрелке начиная с "вверх" до вверх влево
dy = {1, 1, 0, -1, -1, -1, 0, 1};
по всем возможным ходам из массивов(т.е. dx <- dx[i] и dy <- dy[i]):
если a[x + dx][y + dy] == 1 и col[x + dx][y + dy]==0, то
col(col, x + dx, y + dy);
|
На самом деле это поиск в глубину, но его можно легко заменить и на в ширину. Не сильно важно это. 
Ну это была основа, для поиска наибольшего-необходимо хранить наибольшее на данный момент множество, считая в методе col кол-во элементов(или возвращая его рек-но), и иногда обновлять.
P.S. возможны ошибки, но идея правильная, наверное  |
|
|
|
|
Петр : 707
Постоянный посетитель
Откуда: Москва
|
| Дек 17, 2011 13:29 |
| |
|
| нее это обычный треш. покажи код который можно запустить. |
|
|
|
|
PolarHare : 182
Новичок
Откуда: Saint-Petersburg, Russia
|
| Дек 17, 2011 13:34 |
| |
|
| Если вам нужен код, который можно запустить, то у меня будет время где-то вечером. И формализуйте тогда уж, что именно нужно давать на выход. Координаты 1чек из мн-ва/их кол-во/что-то еще. |
|
|
|
|
Петр : 707
Постоянный посетитель
Откуда: Москва
|
| Дек 17, 2011 13:40 |
| |
|
| Петр писал(а): |
есть поле
0 0 0 1 1 1
1 1 0 1 1 0
1 0 0 0 0 0
1 0 0 0 1 1
1 1 1 1 1 0
0 0 0 0 0 0
имеем множество 1.
0 0 0 1 1 1
1 1 0 1 1 0
1 0 0 0 0 0
1 0 0 0 1 1
1 1 1 1 1 0
0 0 0 0 0 0
кол-во входящих единиц 5
множество 2.
0 0 0 1 1 1
1 1 0 1 1 0
1 0 0 0 0 0
1 0 0 0 1 1
1 1 1 1 1 0
0 0 0 0 0 0
кол-во входящих единиц 11.
могу привести еще пример если надо. но вроде все понятно. |
вот тут описано.
мне ТЗ написать нужно? ))
давайте со времен определимся. до какого часа по москве ты успеешь заваять это элементарное задание? )) |
|
|
|
|
PolarHare : 182
Новичок
Откуда: Saint-Petersburg, Russia
|
| Дек 18, 2011 0:19 |
| |
|
| Код: |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class UnitsMaxFind {
public static void main(String[] args) throws IOException {
initUnitsArray();
System.out.println(findMaxGroup());
}
static int n;
static int m;
static int[][] a;
private static void initUnitsArray() throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(in.readLine());
String s = in.readLine();
m = s.length();
a = new int[n + 2][m + 2];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = s.charAt(j - 1) - '0';
}
if (i != n) {
s = in.readLine();
}
}
}
static int[][] col;
static int[] dxAll = {0, 1, 1, 1, 0, -1, -1, -1};
static int[] dyAll = {1, 1, 0, -1, -1, -1, 0, 1};
private static int findMaxGroup() {
col = new int[n + 2][m + 2];
int curCol = 0;
int curMaxSize = 0;
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
if (a[x][y] == 1 && col[x][y] == 0) {
curCol++;
curMaxSize = Math.max(dfs(curCol, x, y), curMaxSize);
}
}
}
return curMaxSize;
}
private static int dfs(int curCol, int x, int y) {
col[x][y] = curCol;
int size = 1;
for (int dInd = 0; dInd < 8; dInd++) {
int dx = dxAll[dInd];
int dy = dyAll[dInd];
if (a[x + dx][y + dy] == 1 && col[x + dx][y + dy] == 0) {
size += dfs(curCol, x + dx, y + dy);
}
}
return size;
}
}
|
Пример ввода и вывода:
5
10001000001
01001000001
10000100011
11111100001
00000000100
12 |
|
|
|
|
Vantuz-Subhuman : 660
Постоянный посетитель
Откуда: издиснейленда
|
| Дек 18, 2011 10:35 |
| |
|
| Петр писал(а): |
в любом случае молодец что что то делаешь.
но задача сильно простая.
а можешь сделать вот такую задачу.
есть радномное поле из 1 и 0
нужно определить самое большое множество единиц.
например
0 0 0 1 1 1
1 1 0 1 1 0
1 0 0 0 0 0
1 0 0 0 1 1
1 1 1 1 1 0
0 0 0 0 0 0
наибольшее множество 11. |
По теме ничего не скажу, но стало интересно.
| Код: |
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) throws Exception {
scan(new int[][]{
{1,1,1,1,1,1,1},
{1,0,0,0,0,0,0},
{1,1,1,1,0,1,1},
{1,0,0,1,0,0,1},
{1,0,0,0,1,0,1},
{1,0,1,0,0,0,1},
{1,0,1,1,1,1,1},
});
scan(new int[][]{
{1,1,1,1,1,1,1},
{1,1,0,0,0,0,0},
{1,1,0,1,0,1,1},
{1,0,0,1,0,0,1},
{1,0,1,0,1,0,1},
{1,0,1,0,0,0,1},
{1,0,1,1,1,1,1},
});
scan(new int[][]{
{1,1,1,1,1,1,1,1},
{1,0,1,0,1,0,1,0},
{1,0,1,0,0,0,1,0},
{0,0,1,0,1,0,0,0},
{1,0,0,0,0,1,0,1},
{0,1,0,1,0,1,0,1},
{1,1,1,1,1,1,1,1},
});
}
private static void scan(int[][] matrix) {
System.out.println("--- Scan :: input matrix: ---");
System.out.println(matToString(matrix));
List<int[][]> bigs = biggestMat(scanGroups(matrix));
int size = -1;
if (bigs.size() > 0) {
size = countSize(bigs.get(0));
}
System.out.println("--- Results: ---");
for (int[][] big : bigs) {
System.out.println("Size: " + size);
System.out.println(matToString(big));
}
}
//////////
// Utils
//////////
private static String matToString(int[][] mat) {
StringBuilder sb = new StringBuilder();
for (int[] row : mat) {
sb.append('[');
for (int i : row) {
sb.append(i > 0 ? '*' : ' ');
sb.append(' ');
}
sb.append(']');
sb.append('\n');
}
return sb.toString();
}
private static List<int[][]> biggestMat(List<int[][]> mats) {
int size, maxsize = -1;
List<int[][]> result = new ArrayList<int[][]>();
for (int[][] mat : mats) {
if (maxsize < 0 | (size = countSize(mat)) >= maxsize) {
if (size > maxsize) {
result.clear();
maxsize = size;
}
result.add(mat);
}
}
return result;
}
private static int countSize(int[][] mat) {
int size = 0;
for (int[] row : mat) {
for (int i : row) {
if (i != 0) {
size++;
}
}
}
return size;
}
////////////////////
// Scanning itself
////////////////////
private static List<int[][]> scanGroups(int[][] mat) {
List<int[][]> models = new ArrayList<int[][]>();
for (int y = 0; y < mat.length; y++) {
x: for (int x = 0; x < mat[y].length; x++) {
if (mat[y][x] != 0) {
for (int[][] model : models) {
if (model[y][x] != 0) {
continue x;
}
}
models.add(scanPoint(mat, y, x, new int[mat.length][mat[y].length]));
}
}
}
return models;
}
private static int[][] scanPoint(int[][] mat, int py, int px, int[][] model) {
if (mat[py][px] != 0 && model[py][px] == 0) {
model[py][px] = 1;
}
for (int y = py - 1; y <= py + 1; y++) {
if (y < 0 || y >= mat.length) {
continue;
}
for (int x = px - 1; x <= px + 1; x++) {
if (x < 0 || x >= mat[y].length) {
continue;
}
if (x == px && y == py) {
continue;
}
if (mat[y][x] != 0 && model[y][x] == 0) {
model[y][x] = 1;
model = scanPoint(mat, y, x, model);
}
}
}
return model;
}
} |
Вывод:
| Код: |
--- Scan :: input matrix: ---
[* * * * * * * ]
[* ]
[* * * * * * ]
[* * * ]
[* * * ]
[* * * ]
[* * * * * * ]
--- Results: ---
Size: 18
[* * * * * * * ]
[* ]
[* * * * ]
[* * ]
[* * ]
[* ]
[* ]
--- Scan :: input matrix: ---
[* * * * * * * ]
[* * ]
[* * * * * ]
[* * * ]
[* * * * ]
[* * * ]
[* * * * * * ]
--- Results: ---
Size: 15
[* * * * * * * ]
[* * ]
[* * ]
[* ]
[* ]
[* ]
[* ]
Size: 15
[ ]
[ ]
[ * * * ]
[ * * ]
[ * * * ]
[ * * ]
[ * * * * * ]
--- Scan :: input matrix: ---
[* * * * * * * * ]
[* * * * ]
[* * * ]
[ * * ]
[* * * ]
[ * * * * ]
[* * * * * * * * ]
--- Results: ---
Size: 16
[* * * * * * * * ]
[* * * * ]
[* * * ]
[ * ]
[ ]
[ ]
[ ]
Size: 16
[ ]
[ ]
[ ]
[ * ]
[* * * ]
[ * * * * ]
[* * * * * * * * ] |
_________________
«One should never underestimate the predictability of stupidity»,
«Never attribute to malice that which can be adequately explained by stupidity» |
|
|
|
|
olenchenko : 21
Новичок
Откуда: Ukraine Donetsk
|
| Дек 19, 2011 9:03 |
| |
|
Задачка от Петра заинтересовала. Задачку можно расширить. Например: все то же только примыканием считать и впритык и через одну клеточку (распределеное множество). А как быстро вы поменяете свои коды для 3-х мерного пространства??? А для 4-х мерного??? А для N-мерного? Ниже предлагаю код для 2D, есть и для ND - если заинетесует выложу.
| Код: |
import java.util.Collections;
import java.util.HashSet;
public class Test {
public static void main(String[] args) {
MyDesk myDesk = new MyDesk(20);
myDesk.findClouds();
myDesk.printResult();
}
}
class MyDesk {
private int size;
private float disp=2f;
private float freq=.2f;
private Point[][] desk;
private HashSet<Cloud> clouds = new HashSet<Cloud>();
private Cloud MaxCloud=null;
public MyDesk(int size){
this.size=size;
this.initDesk(freq);
}
private void initDesk(float freq){
desk = new Point[size][size];
for (int i=0; i<size;i++)
for (int j=0;j< size;j++)
desk[i][j]=new Point(i,j,(int)Math.round(Math.random()-freq));
}
//Расчет поля
void findClouds(){
Point tempMp;
for (int i=0; i<size;i++)
for (int j=0;j< size;j++)
if (desk[i][j].value>0){
tempMp = desk[i][j];
for (Cloud cloud:clouds)
if (cloud.atCloud(tempMp,disp))
cloud.addPoint(tempMp);
//если не вошло не в одно облако то создаем новое
if (tempMp.cloud==null){
Cloud cloud=new Cloud();
cloud.addPoint(tempMp);
clouds.add(cloud);
}
}
}
//вывод поля
public void printResult(){
MaxCloud = Collections.max(clouds);
System.out.println("Size of max: "+MaxCloud.points.size());
for (int i=0; i<size;i++){
for (int j=0; j<size;j++)
System.out.print(" "+(desk[i][j].value==0?"-":desk[i][j].cloud==MaxCloud?"#":"+"));
System.out.println("");
}
}
}
class Cloud implements Comparable<Cloud> {
HashSet<Point> points = new HashSet<Point>();
void addPoint(Point point) {
if (point.cloud==null){
point.cloud = this;
this.points.add(point);
return;
}
if(point.cloud!=this)
union(point.cloud,this);
}
void union(Cloud cloudDst, Cloud cloudSrc){
for(Point p:cloudSrc.points)
p.cloud=cloudDst;
cloudDst.points.addAll(cloudSrc.points);
}
boolean atCloud(Point point, float disp) {
for (Point itPoint : this.points)
if (itPoint.distance(point)<disp)
return true;
return false;
}
@Override
public int compareTo(Cloud o) {
return this.points.size()-o.points.size();
}
}
class Point {
int x;int y;int value;Cloud cloud=null;
Point(int x, int y, int value){
this.x=x; this.y=y; this.value=value;
}
double distance(Point point){
return Math.hypot(point.x-this.x,point.y-this.y);
}
}
|
|
|
|
|
|
RodionGork : 1504
Завсегдатай
Откуда: Saint-Petersburg, Russia
|
| Дек 19, 2011 9:29 |
| |
|
Э, ребя, хватит читерствовать. 
К задачке от Петра не всё является решением, что работает на маленьком поле.  Попробуйте для 1000*1000 что-нибудь разумное написать (тестируйте, скажем, на поле заполненном единственным огромным кластером единичек по спирали или "змейкой")...
| Цитата: |
Например: все то же только примыканием считать и впритык и через одну клеточку (распределеное множество). А как быстро вы поменяете свои коды для 3-х мерного пространства???
|
Это не так принципиально, если сам алгоритм плох %)
UPD: Хотя Ваше решение, кажется, свободно от сверхтормозной проблемы... %)
Последний раз редактировалось: RodionGork (Дек 19, 2011 9:52), всего редактировалось 1 раз |
|
|
|
|
RodionGork : 1504
Завсегдатай
Откуда: Saint-Petersburg, Russia
|
| Дек 19, 2011 9:49 |
| |
|
Автору оригинального сообщения:
| Цитата: |
Если кто-то мне скажет про "повторяющиеся" куски кода, то пусть либо топает мимо, либо попробует хотя бы одну диагональ загнать в один цикл.
...
Насчёт оптимизации отклоняется, и авторы таких сообщений идут лесом. Ибо тут 95% как минимум мозг сломает, увидев первые же индексы, и даже не поймёт, что происходит в программе, даю гарантию.
|
Гы, поменьше патетики, пожалуйста.
Вы просто не очень хорошо продумали как перебирать горизонтали/вертикали/диагонали - или, может, не подметили каких-то свойств Вашей же проверки диагоналей... Поэтому они у вас и выглядят аномально, и Вас же пугают. Как только Вы их упростите, так чтобы перебор всех направлений выглядил "похоже", Вы сами увидите как легко это свернуть в цикл... Цикл должен проходить по массиву определяющему направления в духе:
| Код: |
int[][] dirs = new int[][]{{0, 1}, {1, 0}, {1, 1}, {-1, 1}};
|
Кроме того надо упростить проверку вылета за пределы массива, это можно сделать разными способами, на вкус... %)
По поводу оформления... Ну, просмотрите по-быренькому java code conventions - там всего 20 страниц из них 4 пример оформления... Не пишите название классов с маленькой буквы... Да и вообще если вам нужны все эти классы, сделайте их вложенными в основной. %) |
|
|
|
|
stolzen : 422
Бывалый
Откуда: Нижний Новгород
|
| Дек 19, 2011 16:03 |
| |
|
| RodionGork писал(а): |
| К задачке от Петра не всё является решением, что работает на маленьком поле. Попробуйте для 1000*1000 что-нибудь разумное написать (тестируйте, скажем, на поле заполненном единственным огромным кластером единичек по спирали или "змейкой")... |
Олимпиадными задачками балуетесь?  |
|
|
|
|
Петр : 707
Постоянный посетитель
Откуда: Москва
|
| Дек 19, 2011 16:16 |
| |
|
Вообще это относится к задачам анализа изображения.
например можно усложнить требования. не просто определять множество. а анализировать его как простую фигуру. например квадрат, прямоугольник, круг и так далее. |
|
|
|
|
RodionGork : 1504
Завсегдатай
Откуда: Saint-Petersburg, Russia
|
| Дек 19, 2011 18:37 |
| |
|
| Цитата: |
Олимпиадными задачками балуетесь
|
Олимпиадными бывает (впрочем, наверное, как и у многих) - но в данном случае именно померещилось что задача близка к выделению кластеров на картинке - и тут, сами понимаете, ясно что не должен алгоритм годами работать... %)
Я около года назад что-то такое писал и помню что для ускорения кроме прочего предварительно занижал разрешение картинки, хотя это, пожалуй, не очень хорошо...  |
|
|
|
|
olenchenko : 21
Новичок
Откуда: Ukraine Donetsk
|
| Дек 21, 2011 14:19 |
| |
|
RodionGork Вы правы
| Цитата: |
| К задачке от Петра не всё является решением, что работает на маленьком поле |
100*100 = 7с, 200*200 =105, 1000*1000 устал ждать
| Цитата: |
| тестируйте, скажем, на поле заполненном единственным огромным кластером единичек по спирали |
дало улучшение 100*100 - 2.5с 200*200 = 17с. Причина излишняя обробатываемая информация.
| Цитата: |
| Попробуйте для 1000*1000 что-нибудь разумное написать |
Попробовал два дня убил. Зато тешусь результатом: 100*100
Max Points =10000
Time of execution: 0.188
и 1000*1000
Max Points =1000000
Time of execution: 2.875
| Цитата: |
| UPD: Хотя Ваше решение, кажется, свободно от сверхтормозной проблемы... %) |
?????? |
|
|
|
|
RodionGork : 1504
Завсегдатай
Откуда: Saint-Petersburg, Russia
|
| Дек 22, 2011 7:46 |
| |
|
| Цитата: |
100*100 = 7с, 200*200 =105, 1000*1000 устал ждать
...
и 1000*1000
Max Points =1000000
Time of execution: 2.875
|
Вы имеете в виду что первый результат - это от программы в том виде, как вы её раньше постили, или от какой-то другой? %)
2 секунды на миллион это очень хорошее время, дальше оптимизировать смысла нет. Я так понимаю вы уже довели алгоритм до чего-то близкого к O(n)... Хе-хе... Надо будет теперь мне самому подумать и попробовать. Тоже интересно стало...
Это мне при беглом взгляде показалось что ваши Cloud-сы делают решение более быстрым, чем какое-то из запощенных ранее (типа от перекрашивания спасают)... Но возможно я не вник и ошибся.
В общем, поздравляю! Видимо у вас весьма эффектно получилось поработать над оптимизацией. Это очень-очень хорошо! |
|
|
|
|
|
|
Страница 2 из 3
На страницу Пред. 1, 2, 3 След. |
Список форумов
-> Основы языка Java |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
|
|
