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

Обсуждение задачи 1419. Карта мира 40 островов

what's there in the 18-th test?
Послано DEAL 5 апр 2012 20:54
here is my program, but it doesn't work there, what can be the problem
#include <iostream>
#include <vector>
using namespace std;

#define Max 205

char now[Max];

int nn[Max][Max];
int pp[Max];

char no[20]="Just a picture";
char yes[20]="Island world";

int c=1;

int list[Max*Max][5];

int add(int a, int b)
{
    if(list[a][3]<=2)
    {
        list[a][list[a][3]]=b;
        list[a][3]++;
    }
    else
    {
        cout<<no;
        return -1;
    }
    if(list[b][3]<=2)
    {
        list[b][list[b][3]]=a;
        list[b][3]++;
    }
    else
    {
        cout<<no;
        return -1;
    }
    return 1;
}

int used[Max];
int timer=1;
int tin[Max];
int tup[Max];

int exist=0;

void dfs(int v, int p)
{
    used[v]=1;
    tup[v]=tin[v]=timer;
    timer++;

    for(int i=0; i<3; i++)
    {
        int to=list[v][i];
        if(to==p) continue;
        if(used[to]==1)
            tup[v]=min(tup[v],tin[to]);
        else
        {
            dfs(to,v);
            tup[v]=min(tup[v],tup[to]);
            if(tin[v]<tup[to])
            {
                exist=1;
            }
        }
    }


}

int main()
{
    /* freopen("INPUT.txt","r",stdin);
     freopen("OUTPUT.txt","w",stdout);*/



    int w,h;


    cin>>w>>h;

    if(w%2==0 || h%2==0)
    {
        cout<<no;
        return 0;
    }

    memset(list,0,Max*Max*sizeof(list[0][0]));
    memset(nn,0,Max*Max*sizeof(nn[0][0]));
    memset(used,0,Max*sizeof(used[0]));


    cin.getline(now,w);
    for(int i=0; i<h; i++)
    {
        cin.getline(now,w+1);
        if(now[w-1]<=0)
        {
            cout<<no;
            return 0;
        }

        for(int j=0; j<w; j++)
        {
            if(now[j]=='O')
            {
                nn[i][j]=c;
                c++;
            }
            if(now[j]=='\\') nn[i][j]=-1;
            if(now[j]=='/')     nn[i][j]=-2;
            if(now[j]=='|')  nn[i][j]=-3;
            if(now[j]=='-')     nn[i][j]=-4;
            if(now[j]==' ')  nn[i][j]=-5;

            if(nn[i][j]==0)
            {
                cout<<no;
                return 0;
            }
        }
    }

    for(int i=0; i<h; i++)
    {
        for(int j=0; j<w; j++)
        {
            switch (nn[i][j])
            {
                case -1:
                    if(i==0 || i==h-1 || j==0 || j==w-1)
                    {
                        cout<<no;
                        return 0;
                    }
                    if(nn[i-1][j-1]>0 && nn[i+1][j+1]>0)
                    {
                        if(add(nn[i-1][j-1],nn[i+1][j+1])==-1) return 0;
                    }

                break;

                case -2:
                    if(i==0 || i==h-1 || j==0 || j==w-1)
                    {
                        cout<<no;
                        return 0;
                    }
                    if(nn[i+1][j-1]>0 && nn[i-1][j+1]>0)
                    {
                        if(add(nn[i+1][j-1],nn[i-1][j+1])==-1) return 0;
                    }

                break;

                case -3:
                    if(i==0 || i==h-1 )
                    {
                        cout<<no;
                        return 0;
                    }

                    if(nn[i-1][j]>0 && nn[i+1][j]>0)
                    {
                        if(add(nn[i-1][j],nn[i+1][j])==-1) return 0;
                    }

                break;

                case -4:
                    if(j==0 || j==w-1)
                    {
                        cout<<no;
                        return 0;
                    }
                    if(nn[i][j-1]>0 && nn[i][j+1]>0)
                    {
                        if(add(nn[i][j-1],nn[i][j+1])==-1) return 0;
                    }

                break;

            }

        }


    }
    for(int i=1; i<c; i++)
    {
        if(list[i][3]!=3)
        {
            cout<<no;
            return 0;
        }
    }

    dfs(1,-1);

    if(exist==1)
    {
        cout<<no;
        return 0;
    }

    for(int i=1; i<c; i++)
    {
        if(used[i]==0)
        {
            cout<<no;
            return 0;
        }
    }
    cout<<yes;

}