Sắp xếp ma trận hình xoắn ốc

[boyalone]

Cho 1 ma trận kích thước n x m
Hãy sắp xếp ma trận theo hình xoắn ốc như sau
n,m và chiều sắp xếp do user nhập vào

VD:
Nguồn:
183
476
592

Đích:
123
894
765

Tui ko làm nổi... cao thủ đâu... nhào zô đi.

[unfriendlyboy]

2 biến, 4 vòng for ! xong !

[eagle_in_city]

cái này thuộc KTLT mờ :D
Yeah 4 for....

[bete]

Đi xoa('n o^'c => đi vo`ng theo chu vi 1 hi`nh chu*~ nha^.t (ki'ch thuo*'c gia?m da^`n)

go.i m la` so^' co^.t; n la` so^' do`ng

Ba('t đa^`u đi tu*` vi. tri' (1,1); minX=1, minY=1, maxX=m, maxY=n; đi qua pha?i

đi qua pha?i (co^.t ta(ng da^`n) ne^'u đu.ng maxX thi` gia?m maxX đi 1 & đo^?i
tha`nh đi xuo^'ng duo*'i

đi xuo^'ng duo*'i (do`ng ta(ng da^`n) ne^'u đu.ng maxY thi` gia?m maxY đi 1 & đo^?i tha`nh đi qua tra'i

đi qua tra'i (co^.t gia?m da^`n) ne^'u đu.ng minX thi` ta)ng minX the^m 1 & đo^?i
tha`nh đi le^n tre^n

đi le^n tre^n (do`ng gia?m da^`n) ne^'u đu.ng minY thi` ta(ng minY the^m 1 & đo^?i tha`nh đi qua pha?i

Đi đu? (m*n) buo*'c thi` du*`ng

[ldt116]

Cái này la đề thi IOI từ năm 1900 lâu lắc (khoảng 80 - 88 gì đó) Nó khá dễ mà, nếu bạn cần thì mình gõ cho. Nhưng cho hỏi tí, trong VD, nguồn là gì vậy ? I don't understand !!!

[boyalone]

Là ma trận ban đầu (do user nhập vào chẳng hạn)

[boyalone]

Theo cách của bete, tui đã làm thành công... nhưng hơi dài dòng. Nghe unfriendlyboy
nói thì có vẻ tối ưu quá, vậy sao không post code lên mọi người xem với

Cách của tui:

var temp: array[1..100]of byte;
a: array[1..10,1..10]of byte;
i,j,k,n,m, minX,minY,maxX,maxY,h:byte;

procedure View;
begin
{Hien thi ma tran}
for i:=1 to n do
begin
for j:=1 to m do
begin
write(a[i,j]:8);
end;
writeln;
writeln;
end;
end;

begin
write('Nhap so hang n:');readln(n);
write('Nhap so cot m:');readln(m);
write('Ban muon nhap du lieu cho ma tran hay muon chuong trinh tu tao ra? [1,0]');readln(i);
if i=0 then {Tu dong tao ra}
begin
randomize;
for i:=1 to n do
for j:=1 to m do
begin
a[i,j]:=random(999);
end;
end
else
begin
for i:=1 to n do
for j:=1 to m do
begin
write('a[',i,',',j,']: ');readln(a[i,j]);
end;
end;
Writeln('Ma tran ban dau:');
View;
{Chuyen sang mang 1 chieu temp}
for i:=1 to n do
for j:=1 to m do
begin
k:=k+1;
temp[k]:=a[i,j];
end;

{Sap xep mang temp}
for i:=1 to m*n-1 do
for j:=i+1 to m*n do
if temp[i]>temp[j] then
begin
k:=temp[i];
temp[i]:=temp[j];
temp[j]:=k;
end;

{Chuyen mang Temp thanh ma tran}
minX:=1;
minY:=2;
maxX:=m;
maxY:=n;
i:=1;
j:=0;
h:=1;
for k:=1 to m*n do
begin
if h=1 then j:=j+1;{right}
if h=2 then i:=i+1;{down}
if h=3 then j:=j-1;{left}
if h=4 then i:=i-1;{up}
a[i,j]:=temp[k];
if (j=maxX)and(h=1) then{->down}
begin
maxX:=maxX-1;
h:=2;
end;
if (j=minX)and(h=3) then{->up}
begin
minX:=minX+1;
h:=4;
end;

if (i=maxY)and(h=2) then{->left}
begin
maxY:=maxY-1;
h:=3;
end;
if (i=minY)and(h=4) then{->right}
begin
minY:=minY+1;
h:=1;
end;

end;
Writeln('Ma tran sau khi sap xep:');
View;
readln;
end.

[hiepsi4rum]

hình như là như vậy :
đầu tiên bạn nhập giá trị bất kì vào ma trận(m x m),
sắp xếp các giá trị đó -> có thể bạn chép giá trị của ma trận vào 1 mảng
cuối cùng là xuất ma trận theo hình xoán ốc -> kỹ thuật lập trình

[bete]

boyalone cho góp ý 1 tí nhé:

if h=1 then j:=j+1;{right}
if h=2 then i:=i+1;{down}
if h=3 then j:=j-1;{left}
if h=4 then i:=i-1;{up}

nên sửa là

if h=1 then j:=j+1 {right}
else if h=2 then i:=i+1 {down}
else if h=3 then j:=j-1 {left}
else if h=4 then i:=i-1 {up}

tương tự:

if (j=maxX)and(h=1) then{->down}
........
else if (j=minX)and(h=3) then{->up}
........
else if (i=maxY)and(h=2) then{->left}
........
else if (i=minY)and(h=4) then{->right}

vì mình có 1 vòng lặp for

Đô'i với bài này co thể nó 0 giúp chương trình chạy nhanh hơn gì nhưng đó là 1 thói
quen lập trinh tô't :)

1 cách nữa để đơn giản hóa

if h=1 then j:=j+1 {right}
else if h=2 then i:=i+1 {down}
else if h=3 then j:=j-1 {left}
else if h=4 then i:=i-1 {up}

là khai báo 2 mảng:
dx = 0, 1, 0, -1
dy = 1, 0, -1, 0

và xài:

i := i + dx[h];
j := j + dy[h];

:)

[unfriendlyboy]

Cách làm này của bạn chưa được hay lắm. Để mình post cách làm của mình nên nghen. Chờ 1 tí :)

[unfriendlyboy]

Đây nè:


uses crt;
type arr=array[1..10,1..10] of integer;
var a:arr;
i,j,x,y,n:integer;
dem,bd,kt:integer;
begin
textmode(c80);
clrscr;
n:=5;

dem:=0; bd:=1; kt:=n;
for i:=1 to n do
for j:=1 to n do
a[i,j]:=(i-1)*n+j;
while bd<kt do
begin
for x:=bd to kt-1 do write(a[bd,x]:3);
for y:=bd to kt-1 do write(a[y,kt]:3);
for x:=kt downto bd+1 do write(a[kt,x]:3);
for y:=kt downto bd+1 do write(a[y,bd]:3);
inc(bd); dec(kt);
end;
readln;
end.

[unfriendlyboy]

Biến bd -> Bắt đầu
kt -> Kết thúc

[bete]

Cách giải của unfriendlyboy ngắn gọn lắm ! Dùng 4 vòng for để cài đặt đi qua phải, đi xuống, đi qua trái, đi lên ==> thật gọn !!!

Tuy nhiên, nêu thay vì là ma trận vuông mà là ma trận thì chữ nhật thì phai sửa lại 1 chút
& nhớ coi chừng:
nếu chiều rộng (số cột) lớn hơn chiều cao (số dòng) => ở lần cuối cùng mình có thể chỉ còn 1 ma trận 1 dòng => phải thêm 1 cái if !?

Tương tụ: nếu chiều cao (số dòng) lớn hơn chiều rộng (số cột) => ở lần cuối cùng mình có thể chỉ còn 1 ma trận 1 cột => phải thêm 1 cái if !?

[unfriendlyboy]

Uhm, đúng rồi, em làm cái này cho ma trận vuông mà. Nếu hcn thì sửa lại 1 tí là xong :)

[FanIT]

Toi thay rang cach cac ban chi de sap xep ma tran cac phan tu tu 1 den n*n thoi. Toi co 1 bai la cho 1 mang 2 chieu (cac phan tu la cac so bat ki) va sap xep tang dan theo hinh xoan oc. Toi da lam thu, nhung hoi dai nen toi chua biet cach post len, ban nao chi toi cach de toi post len cho cac ba xem thu

[unfriendlyboy]

Trời, nhìn bài mình mà bạn ko biết sửa lại huh ? :(

[thangtien97]

Các bác làm dài wa', cách của em ngắn gấp bội lè mà vẵn đúng:
procedure Gen_Spiral(var A: matrix; m, n: integer);
var x, y, seed, count, direct, total: integer;
begin
direct := 4;
total := m*n;
count := 0;
x := 0;
y := 1;
for seed := 1 to total do begin
while count = 0 do
case direct of
1, 3: begin inc(direct); dec(n); count := m; end;
2, 4: begin
inc(direct); dec(m); count := n;
if direct = 5 then direct := 1;
end;
end;
case direct of
1: inc(x);
2: inc(y);
3: dec(x);
4: dec(y);
end;
dec(count);
a[y, x] := seed;
end;
end;

[onlyloneblack]

thanks bạn nhé, hjhjhjhj

[congcuong_vippro]

=)) nhìu cao thủ vãi chưỡng