NK05EOPR - Đổi chỗ

[sample (<script>alert("hacked")</script>)]

Đề 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\n",InQueue[tmp]);
                    found=true;
                    break;
                }

                if(!InQueue[s])
                {
                    lq.push(s);
                    InQueue[s]=InQueue[tmp]+1;
                    //printf("%s\n",s.c_str());
                }
            }
            if(found) break;
        }
        //printf("%s\n",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??

[sample (<script>alert("hacked")</script>)]

Xin giúp em.
@david15894
@Gio

[sample (<script>alert("hacked")</script>)]

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

[Mai_Huu (Mai Hữu)]

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

[AI_Android]

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

[sample (<script>alert("hacked")</script>)]

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?

[Gio (Gió)]

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

[tcm (Người bí ẩn)]

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ứ

[vuthanhplus (Vũ Thanh)]

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

[AI_Android]

chẳng hạn dùng hamming distance

[AI_Android]

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ả =))

[yuh (Huy)]

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

[AI_Android]

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

[Tulip (lx)]

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

[sample (<script>alert("hacked")</script>)]

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.

[tntxtnt]

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

[sample (<script>alert("hacked")</script>)]

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

[tntxtnt]

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 ~.~

[sample (<script>alert("hacked")</script>)]

tính điểm

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

[AI_Android]

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