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??
Bài liên quan
Xin giúp em.
@david15894
@Gio
Ơ?
Thế là không ai giải ra à? @@
chính xác là chả ai thèm quan tâm
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
Thế làm sao biết cái nào có khả năng?
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
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ứ
Chẳng có mấy ai giải
chẳng hạn dùng hamming distance
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ả =))
Bài này có một cách khác là dùng mảng 3D
Nghe lạ vậy bạn có thể chia sẻ rõ hơn không
Mình quen xài python nên ít làm mấy bài này, vì toàn quá thừoi gian :))
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.
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
Cô lên anh,
while not success do try_againvừ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 ~.~
là cái gì vậy anh?
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
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
cái copy_if đầu tiên là copy đúng cái
inà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