30/09/2018, 22:25

NK05EOPR - Đổi chỗ

Đề bài ở đây: http://vn.spoj.com/problems/NK05EOPR/
Code của em đây, nhưng chạy quá thời gian?

#include <bits/stdc++.h>
using namespace std;

const string ok="abcdefghijkl";

int main()
{
    // Tim xem dinh x co the thay doi voi dinh y nao?
    int a[12][12];
    memset(a,0,sizeof(a));
    int d[5]={0,1,3,6,12};

    for(int i=0; i<=11; i++)
        for(int j=0; j<=11; j++)
            if(i!=j)
            {
                int x=abs(i-j);
                int k=0;
                for(int ii=1; ii<=3; ii++)
                    if(x==d[ii])
                    {
                        k=ii;
                        break;
                    }
                if(k==0) continue;
                if(int(i/d[k+1])==int(j/d[k+1]))
                {
                    a[i][0]++;
                    a[i][a[i][0]]=j;
                }
            }

    // Nhap du lieu
    int T;
    scanf("%d",&T);
    while(T--)
    {
        string input="";
        for(int i=0; i<12; i++)
        {
            int x;
            scanf("%d",&x);
            //chuyen day so thanh dang xau
            input+=char(x+int('a'));
        }

        // Duyet theo chieu rong BFS
        unordered_map <string,int> InQueue;
        InQueue[input]=1;
        queue<string> lq;
        bool found=false;

        for(lq.push(input); !lq.empty(); lq.pop())
        {
            string tmp=lq.front();
            int zero=tmp.find("a");
            for(int i=1; i<=a[zero][0]; i++)
            {
                string s=tmp;
                swap(s[zero],s[a[zero][i]]);
                if(s==ok)
                {
                    printf("%d
",InQueue[tmp]);
                    found=true;
                    break;
                }

                if(!InQueue[s])
                {
                    lq.push(s);
                    InQueue[s]=InQueue[tmp]+1;
                    //printf("%s
",s.c_str());
                }
            }
            if(found) break;
        }
        //printf("%s
",input.c_str());
    }


    return 0;
}

Chả nhẽ mấy nghìn thành viên của diễn đàn Dạy Nhau Học không giải nổi bài toán này??

hacked viết 00:30 ngày 01/10/2018

Xin giúp em.
@david15894
@Gio

hacked viết 00:30 ngày 01/10/2018

Ơ?
Thế là không ai giải ra à? @@

Mai Hữu viết 00:30 ngày 01/10/2018

chính xác là chả ai thèm quan tâm

Ai Android viết 00:41 ngày 01/10/2018

Nghĩ thêm 1 cái hàm tính giá trị của trạng thái nữa
Khi BFS thì ưu tiên duyệt cái nào có khả năng trước.
btw: cách bạn làm rất hay

hacked viết 00:36 ngày 01/10/2018

Khi BFS thì ưu tiên duyệt cái nào có khả năng trước.

Thế làm sao biết cái nào có khả năng?

Gió viết 00:31 ngày 01/10/2018

Khi dãy a đã dc sắp xếp thì a[i]==i để đảm bảo dãy tăng. Do đó sẽ ưu tiên duyệt cái nào thoã mãn dk đó hơn

Người bí ẩn viết 00:40 ngày 01/10/2018

Chả nhẽ mấy nghìn thành viên của diễn đàn Dạy Nhau Học không giải nổi bài toán này??

Chắc vì câu này mà Topic bạn ít người trả lời hoặc lâu có người vào trả lời.
Kiên nhẫn đi chứ

Vũ Thanh viết 00:34 ngày 01/10/2018

Chẳng có mấy ai giải

Ai Android viết 00:38 ngày 01/10/2018

chẳng hạn dùng hamming distance

Ai Android viết 00:35 ngày 01/10/2018

mình nghĩ chủ thớt có ý muốn đánh đố thì đúng hơn thấy bài này cũng chỉ có mấy người làm đc mà mấy cái này lên group vnoi hỏi thì chắc bị chửi hả =))

X viết 00:30 ngày 01/10/2018

Bài này có một cách khác là dùng mảng 3D

Ai Android viết 00:33 ngày 01/10/2018

Nghe lạ vậy bạn có thể chia sẻ rõ hơn không

lx viết 00:38 ngày 01/10/2018

Mình quen xài python nên ít làm mấy bài này, vì toàn quá thừoi gian :))

hacked viết 00:30 ngày 01/10/2018

Mời anh @tntxtnt vào xem thử.
Em không có ý bóc lột khả năng của anh, em chỉ thấy anh có cùng đam mê và rất giỏi. anh có thể xem bài này giúp em được không? Em làm mãi mà không AC đựoc.

‏ viết 00:36 ngày 01/10/2018

bài này khó ở chỗ tính điểm của mỗi hoán vị, có lẽ bó tay, lần này lỗ kim nhỏ quá chui qua ko lọt

hacked viết 00:34 ngày 01/10/2018

Cô lên anh, while not success do try_again

‏ viết 00:39 ngày 01/10/2018

vừa nộp thử cái test, chạy quá thời gian. Tính điểm theo cách thông thường là đi so sánh mảng. Phải có cách tính điểm tốt hơn mới được ~.~

hacked viết 00:41 ngày 01/10/2018

tính điểm

là cái gì vậy anh?

Ai Android viết 00:28 ngày 01/10/2018

vẫn chưa xong à để tối về code thử xem =))
có 1 hướng khác là bạn có thể thử tham lam, bằng cách cố định 1 số vị trí loang các vị trí còn lại

‏ viết 00:40 ngày 01/10/2018

có 1 hướng khác là bạn có thể thử tham lam, bằng cách cố định 1 số vị trí loang các vị trí còn lại

mình thử luôn rồi, cố định mấy số đúng vị trí rồi, chỉ thay đổi các số còn lại thôi. Vẫn quá thời gian

void zeroSwappableIndices(int from)
{
    int best = zeroIndex();
    auto swappableIndices = zeroNeighbors[best];
    neighbors.clear();
    std::copy_if(begin(swappableIndices), end(swappableIndices),
        std::back_inserter(neighbors), [best](int i){
            return i == best;
    });
    if (neighbors.empty())
        std::copy_if(begin(swappableIndices), end(swappableIndices),
            std::back_inserter(neighbors), [from,this](int i){
                return i != from && i != this->data[i];
        });
}

cái copy_if đầu tiên là copy đúng cái i nào có giá trị trùng với vị trí của số 0. Nếu có thì return cái này để tiếp theo swap đúng nó luôn. Nếu ko có thì cái copy_if thứ 2 copy những giá trị i mà ko đúng vị trí với trị số của nó (khác from nữa để khỏi bị ngược). Rồi Dijkstra tiếp mấy neighbors này. Vậy mà vân quá thời gian chạy lên tới 950MB mem Mấy cái AC toàn vài MB mem chắc có công thức gì rồi

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

hacked

0 chủ đề

0 bài viết

Tác giả nổi bật