T1.1 Di chuyển từ Tây sang Đông

Được sửa bởi Admin ngày Wed Apr 27, 2022 10:40 pm; sửa lần 1.

T1. Di chuyển từ Tây sang Đông
Cho hình chữ nhật M x N ô vuông (các hàng đánh số từ 1 đến M từ trên xuống và các cột đánh số từ 1 đến N từ trái sang phải), mỗi ô vuông chứa một số nguyên. Con kiến có thể di chuyển từ một ô sang một ô khác thuộc cột bên phải cùng dòng hoặc lệch một dòng. Con kiến đang đứng ở cột 1, muốn di chuyển sang cột N. Hãy tìm cách di chuyển từ cột 1 sang cột N sao cho tổng các số của các ô con kiến đi qua là nhỏ nhất.
Input: Từ file văn bản WTOE.INP
• Dòng đầu tiên chứa hai số nguyên M, N (1≤M,N≤100)
• Tiếp theo là M dòng, mỗi dòng ghi N số nguyên là các số nằm trên các ô vuông của hàng tương ứng bắt đầu từ cột 1 đến cột N. Các số nguyên này có giá trị tuyệt đối không vượt quá 30000
Output: Ghi ra file văn bản WTOE.OUT
• Dòng thứ nhất ghi tổng các số trong các ô đi qua
• Dòng thứ 2 ghi N số lần lượt là chỉ số hàng của các ô trên hành trình bắt đầu từ cột 1 đến cột N
Ví dụ:
WTOE.INP
5 4
21 56 2 8
4 3 6 344
235 52 7 2
45 6 2 6
56 32 62 2
WTOE.OUT
15
2 2 2 3

MrT BQT 16:03:01 27.04.2022

Tiêu đề: Code tham khảo viết bằng NNLT Pascal Wed Apr 27, 2022 4:14 pm

Code:: Const    finp    = 'WTOE.inp';
   fout    = 'WTOE.out';
Maxmax = 10000000;
Maxn = 11;

Var    fi,fo    : Text;
a,f : Array [0..Maxn,0..Maxn] of Longint;
m,n : Integer;

Procedure Nhap;
Var i,j : Integer;
Begin
Readln(fi,m,n);
For i:=0 to m+1 do
For j:=0 to n do a[i,j]:=maxmax;
For i:=1 to m do
For j:=1 to n do Read(fi,a[i,j]);
f:=a;
End;

Procedure Chuanbi;
Begin

End;

Function Min ( x,y,z : Longint ) : Longint;
Begin
If x<y then y:=x;
If z<y then Min:=z Else min:=y;
End;

Procedure Xuli;
Var i,j,p,q : Integer;
kq : Longint;
Begin
kq:=10*maxmax;
For j:=n-1 Downto 1 do
For i:=1 to m do
Inc(F[i,j],Min(F[i+1,j+1],F[i-1,j+1],f[i,j+1]));
Kq:=F[1,1];
For j:=1 to m do
If Kq>F[j,1] then
Begin
i:=j;Kq:=F[j,1];
End;
Writeln(fo,kq);
For j:=1 to n-1 do
Begin
Write(fo,i,#32);
If F[i,j]=F[i+1,j+1]+a[i,j] then i:=i+1;
If F[i,j]=F[i-1,j+1]+a[i,j] then i:=i-1;
End;WRite(fo,i);
End;

Begin
Assign(fi,finp);Reset(fi);
Assign(fo,fout);Rewrite(fo);
Nhap;
Chuanbi;
Xuli;
Close(fi);Close(fo);
End.

Tổng số bài gửi : 12 Join date : 03/05/2022

#include <bits/stdc++.h>
#define N 107
#define INF 30000000

using namespace std;

int n, m;
int a[N][N], f[N][N];

void DP () {
for (int j = 0; j <= m+1; ++j) f[0][j] = f[n+1][j] = INF;

for (int j = 1; j <= m; ++j) {
for (int i = 1; i <= n; ++i) {
f[i][j] = min (f[i][j-1], min (f[i-1][j-1], f[i+1][j-1])) + a[i][j];
}
}

int pos = n;
for (int i = 1; i <= n; ++i) if (f[i][m] < f[pos][m]) pos = i;
cout << f[pos][m] << '\n';
stack <int> res;
for (int j = m; j > 0; --j) {
for (int k = 0; k < 3; ++k) {
int p = pos+k-1;
int tmp = f[pos][j] - a[pos][j];
if (f[p][j-1] == tmp) {
res.push (pos);
pos = p;
break;
}
}
}
while (res.size()) cout << res.top() << ' ', res.pop();
}

int main () {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
freopen ("WTOE.INP", "r", stdin);
freopen ("WTOE.OUT", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) cin >> a[i][j];

DP ();
return 0;
}

Tổng số bài gửi : 9 Join date : 08/05/2022

#include<bits/stdc++.h>
#define N 101
using namespace std;
const int h=INT_MAX;
int a[N][N],d[N][N],tr[N][N]; int m,n,ans=0,res=h;
void inp(){
cin>>m>>n;
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++) cin>>a[i][j];
for(int i=1; i<=n; i++) d[0][i]=d[m+1][i]=h;
for(int i=1; i<=m; i++) d[i][n]=a[i][n];
}
void solve(){
for(int j=n-1; j>0; j--)
for(int i=1; i<=m; i++){
d[i][j]=d[i-1][j+1];
tr[i][j]=i-1;
if(d[i][j]>d[i][j+1]){
d[i][j]=d[i][j+1];
tr[i][j]=i;
}else if(d[i][j]>d[i+1][j+1]){
d[i][j]=d[i+1][j+1];
tr[i][j]=i+1;
}
d[i][j]+=a[i][j];
}
for(int i=1; i<=m; i++)
if(res>d[i][1]){
res=d[i][1]; ans=i;
}
cout<<res<<"\n";
for(int i=1; i<=n; i++){
cout<<ans<<" ";
ans=tr[ans][i];
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("wtoe.inp","r",stdin);
freopen("wtoe.out","w",stdout);
inp();
solve();
}

Tổng số bài gửi : 34 Join date : 08/05/2022

#include<bits/stdc++.h>
#define nmax 107

using namespace std;

int n, m;
int a[nmax][nmax], f[nmax][nmax], t[nmax][nmax];
int res = 0;
int x;

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> a[i][j];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
if(j == 0)
f[i][j] = a[i][j];
else{
int pre = f[i][j-1];
t[i][j] = i;
if(pre < f[i-1][j-1]){
pre = f[i-1][j-1];
t[i][j] = i-1;
}
if(pre < f[i+1][j-1]){
pre = f[i+1][j-1];
t[i][j] = i+1;
}
f[i][j] = pre + a[i][j];
}
}
int r;
for(int i = 1; i <= n; i++)
if(f[i][m] < res){
res = f[i][m];
r = i;
}
cout << res << '\n';
for(int i = 1; i <= n; i++){
cout << r << ' ';
r = t[r][i];
}
return 0;
}

Tiêu đề: Re: T1.1 Di chuyển từ Tây sang Đông Mon May 09, 2022 9:26 pm

- Gọi F[i,j] là tổng các số của các ô con kiến đi qua nhỏ nhất để đến ô (i,j).
- Các ô đi đến được ô (i,j) gồm: (i-1,j-1), (i, j-1), (i+1,j-1).
- F[i,j] = GTNN(F[i-1,j-1], F[i,j-1], F[i+1,j-1]) + a[i,j].
- F[0,0] = 0
- Vì con kiến xuất phát từ cột 1 đi đến cột N nên F[i,1] = a[i,1].
- Giá trị nhỏ nhất nằm ở cột thứ N: a[i, N].
- Kết quả của bài toán là giá trị nhỏ nhất của (a[i,N]): res = min(res, a[i,N])
- Lưu ý: For (j) trước, For(i).
- Đánh giá độ phức tạp thuật toán: O(m.n).

Code:: #include<bits/stdc++.h>
#define N 101
using namespace std;
const int h=INT_MAX;
int a[N][N],d[N][N],tr[N][N]; int m,n,ans=0,res=h;
void inp(){
cin>>m>>n;
for(int i=1; i<=m; i++)
   for(int j=1; j<=n; j++) cin>>a[i][j];
for(int i=1; i<=n; i++) d[0][i]=d[m+1][i]=h;
for(int i=1; i<=m; i++) d[i][n]=a[i][n];
}
void solve(){
for(int j=n-1; j>0; j--)
   for(int i=1; i<=m; i++){
      d[i][j]=d[i-1][j+1];
      tr[i][j]=i-1;
      if(d[i][j]>d[i][j+1]){
         d[i][j]=d[i][j+1];
         tr[i][j]=i;
      }else if(d[i][j]>d[i+1][j+1]){
         d[i][j]=d[i+1][j+1];
         tr[i][j]=i+1;
      }
      d[i][j]+=a[i][j];
   }
for(int i=1; i<=m; i++)
   if(res>d[i][1]){
      res=d[i][1]; ans=i;
   }
cout<<res<<"\n";
for(int i=1; i<=n; i++){
   cout<<ans<<" ";
   ans=tr[ans][i];
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("wtoe.inp","r",stdin);
freopen("wtoe.out","w",stdout);
inp();
solve();
return 0;
}

Tiêu đề: Re: T1.1 Di chuyển từ Tây sang Đông Mon May 09, 2022 9:33 pm

» Trần Đồng Nguyệt Ánh
» Trần Đồng Nguyệt Ánh
» Trần Đồng Nguyệt Ánh
» Trần Đồng Nguyệt Ánh
» bài 6- chuyên đề 1