Hướng dẫn giải của Cắt hình chữ nhật
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; dx:array[1..4] of longint=(-1,0,1,0); dy:array[1..4] of longint=(0,1,0,-1); maxn=440; oo:int64=1000000000; var m,n,sd,nh:longint; doc,ngang:array[0..maxn,0..maxn] of longint; pos,cur,h,p:array[1..maxn*maxn] of longint; d:array[1..maxn*maxn] of int64; a,c:array[1..maxn*maxn*4+maxn*4] of longint; stt:array[0..maxn,0..maxn] of longint; free:array[1..maxn*maxn] of boolean; re:int64; procedure rf; var i,j:longint; begin read(m,n); if (m=1) and (n=1) then begin writeln(-1); halt; end; for i:=1 to m do for j:=1 to n-1 do read(doc[i,j]); for i:=1 to m-1 do for j:=1 to n do read(ngang[i,j]); end; function calc(i,j,ii,jj:longint):longint; begin if i=ii then begin if j>jj then calc:=ngang[i,j] else calc:=ngang[i,jj]; end else begin if i>ii then calc:=doc[i,j] else calc:=doc[ii,j]; end; end; procedure init; var i,j,x,ii,jj,xx,k,sl:longint; begin sd:=4; for i:=1 to m-1 do for j:=1 to n-1 do begin inc(sd); stt[i,j]:=sd; end; for i:=1 to m-1 do begin stt[i,0]:=1; stt[i,n]:=3; end; for j:=1 to n-1 do begin stt[0,j]:=4; stt[m,j]:=2; end; pos[1]:=1; for i:=1 to m-1 do begin x:=stt[i,1]; a[i]:=x; c[i]:=ngang[i,1]; end; pos[2]:=pos[1]+m-1; for j:=1 to n-1 do begin x:=stt[m-1,j]; a[pos[2]+j-1]:=x; c[pos[2]+j-1]:=doc[m,j]; end; pos[3]:=pos[2]+n-1; for i:=1 to m-1 do begin x:=stt[i,n-1]; a[pos[3]+i-1]:=x; c[pos[3]+i-1]:=ngang[i,n]; end; pos[4]:=pos[3]+m-1; for j:=1 to n-1 do begin x:=stt[1,j]; a[pos[4]+j-1]:=x; c[pos[4]+j-1]:=doc[1,j]; end; sl:=n-1; for i:=1 to m-1 do for j:=1 to n-1 do begin x:=stt[i,j]; pos[x]:=pos[x-1]+sl; for k:=1 to 4 do begin ii:=i+dx[k]; jj:=j+dy[k]; xx:=stt[ii,jj]; a[pos[x]+k-1]:=xx; c[pos[x]+k-1]:=calc(i,j,ii,jj); end; sl:=4; end; pos[sd+1]:=pos[sd]+sl; end; procedure update(x:longint); var cha,con:longint; begin con:=p[x]; if con=0 then begin inc(nh); con:=nh; end; cha:=con shr 1; while (cha>0) and (d[h[cha]]>d[x]) do begin h[con]:=h[cha]; p[h[con]]:=con; con:=cha; cha:=con shr 1; end; h[con]:=x; p[x]:=con; end; function pop:longint; var x,cha,con:longint; begin pop:=h[1]; x:=h[nh]; dec(nh); cha:=1; con:=2; while (con<=nh) do begin if (con<nh) and (d[h[con+1]]<d[h[con]]) then inc(con); if d[h[con]]>=d[x] then break; h[cha]:=h[con]; p[h[cha]]:=cha; cha:=con; con:=cha shl 1; end; h[cha]:=x; p[x]:=cha; end; procedure dijk(x:longint); var i,j,y,t:longint; begin for i:=1 to sd do begin free[i]:=true; d[i]:=oo; end; fillchar(p,sizeof(p),0); nh:=0; d[x]:=0; t:=x; update(x); repeat x:=pop; free[x]:=false; if (x<>t) and (x<5) then continue; for i:=pos[x] to pos[x+1]-1 do begin y:=a[i]; if d[y]>d[x]+c[i] then begin d[y]:=d[x]+c[i]; update(y); end; end; until (not free[3]) or (not free[4]); if d[3]<re then re:=d[3]; if d[4]<re then re:=d[4]; end; procedure pr; begin oo:=oo*oo; re:=oo; dijk(1); dijk(2); writeln(re); end; begin assign(input,fi); reset(input); rf; init; pr; close(input); end.
Code mẫu của ladpro98
{$MODE OBJFPC} program cutrect; uses math; type e=record x,y:longint; w:int64; end; const fi=''; maxn=444; oo=high(int64); var lr,ud:array[0..maxn,0..maxn] of int64; d:array[0..maxn,0..maxn] of int64; pos:array[0..maxn,0..maxn] of longint; h:array[0..maxn*maxn] of e; m,n,nh:longint; res:int64; procedure input; var inp:text; i,j:longint; begin assign(inp,fi); reset(inp); readln(inp,m,n); //if (m=1) and (n=1) then begin write(-1); halt; end; inc(m);inc(n); for i:=1 to m-1 do begin for j:=2 to n-1 do read(inp,ud[i,j]); readln(inp); end; for i:=2 to m-1 do begin for j:=1 to n-1 do read(inp,lr[i,j]); readln(inp); end; close(inp); end; function getAdj(k,i,j:longint):e; var t:e; begin //if j=0 then writeln('shit'); if k=1 then begin t.x:=i-1; t.y:=j; t.w:=ud[i-1,j]; end else if k=2 then begin t.x:=i; t.y:=j+1; t.w:=lr[i,j]; end else if k=3 then begin t.x:=i+1; t.y:=j; t.w:=ud[i,j]; end else if k=4 then begin t.x:=i; t.y:=j-1; t.w:=lr[i,j-1]; end; exit(t); end; procedure update(v:e); var p,c:longint; begin c:=pos[v.x,v.y]; if c=0 then begin inc(nh); c:=nh; end; repeat p:=c div 2; if (p=0) or (d[h[p].x,h[p].y]<=d[v.x,v.y]) then break; h[c]:=h[p]; pos[h[c].x,h[c].y]:=c; c:=p; until false; h[c]:=v; pos[v.x,v.y]:=c; end; function extract:e; var v:e; p,c:longint; begin result:=h[1]; v:=h[nh]; dec(nh); p:=1; repeat c:=2*p; if (c<nh) and (d[h[c+1].x,h[c+1].y]<d[h[c].x,h[c].y]) then inc(c); if (c>nh) or (d[v.x,v.y]<=d[h[c].x,h[c].y]) then break; h[p]:=h[c]; pos[h[p].x,h[p].y]:=p; p:=c; until false; h[p]:=v; pos[v.x,v.y]:=p; end; function inBound(i,j:longint):boolean; begin if ((i=1) and (j=1)) or ((i=m) and (j=n)) then exit(false); exit((1<=i) and (i<=m) and (1<=j) and (j<=n)); end; function last(i,j:longint):boolean; begin if (i=1) and (2<=j) and (j<n) then exit(true); if (j=n) and (2<=i) and (i<m) then exit(true); exit(false); end; function toE(i,j:longint):e; var t:e; begin t.x:=i; t.y:=j; exit(t); end; procedure init; var i,j:longint; begin for i:=1 to m do for j:=1 to n do d[i,j]:=oo; for i:=2 to m-1 do begin d[i,1]:=0; update(toE(i,1)); end; for i:=2 to n-1 do begin d[m,i]:=0; update(toE(m,i)); end; for i:=1 to n-1 do begin lr[1,i]:=oo; lr[m,i]:=oo; end; for i:=1 to m-1 do begin ud[i,1]:=oo; ud[i,n]:=oo; end; res:=oo; end; procedure dijkstra; var u,v:e; i:longint; begin update(toE(1,1)); repeat u:=extract; if last(u.x,u.y) then res:=min(res,d[u.x,u.y]); for i:=1 to 4 do begin v:=getAdj(i,u.x,u.y); if inBound(v.x,v.y) then if d[v.x,v.y]-v.w>d[u.x,u.y] then begin d[v.x,v.y]:=d[u.x,u.y]+v.w; update(v); end; end; until nh=0; end; begin input; init; dijkstra; if res=oo then res:=-1; write(res); end.
Code mẫu của RR
uses math; const MAXN=411; oo=1000111000111; var i,j,m,n,u,v:longint; hpos,d,cot,hang:array[1..411,1..411] of int64; res:int64; hu,hv:array[1..411*411] of longint; hsize:longint; procedure swap(var a,b:longint); inline; var tmp:longint; begin tmp:=a; a:=b; b:=tmp; end; procedure swapi(var a,b:int64); inline; var tmp:int64; begin tmp:=a; a:=b; b:=tmp; end; procedure swapH(a,b:longint); inline; begin swapi(hpos[hu[a],hv[a]], hpos[hu[b],hv[b]]); swap(hu[a],hu[b]); swap(hv[a],hv[b]); end; function lower(a,b:longint):boolean; inline; begin exit( d[hu[a],hv[a]] < d[hu[b],hv[b]]); end; procedure down(i:longint); inline; var j:longint; begin j:=i shl 1; while (j<=hsize) do begin if (j<hsize) and lower(j+1,j) then inc(j); if lower(j,i) then begin swapH(i,j); i:=j; j:=i shl 1; end else exit; end; end; procedure up(i:longint); inline; var j:longint; begin j:=i shr 1; while (i>1) and lower(i,j) do begin swapH(i,j); i:=j; j:=i shr 1; end; end; procedure push(u,v:longint); inline; begin inc(hsize); hu[hsize]:=u; hv[hsize]:=v; hpos[u,v]:=hsize; up(hsize); end; procedure pop(var u,v:longint); inline; begin u:=hu[1]; v:=hv[1]; swap(hu[1],hu[hsize]); swap(hv[1],hv[hsize]); hpos[hu[1],hv[1]]:=1; dec(hsize); down(1); end; procedure update(u,v:longint; k:int64); begin if d[u,v]>k then begin d[u,v]:=k; if hpos[u,v]=0 then push(u,v) else up(hpos[u,v]); end; end; procedure ijk; begin while (hsize>0) do begin pop(u,v); if ((v=1) and (u>=2)) or ((u=m+1) and (v<=n)) then begin res:=min(res,d[u,v]); break; end; if (u>=2) and (u<=m) and (v>=2) and (v<=n+1) then update(u,v-1,d[u,v]+hang[u-1,v-1]); if (u>=2) and (u<=m) and (v>=1) and (v<=n) then update(u,v+1,d[u,v]+hang[u-1,v]); if (u>=2) and (u<=m) and (v>=2) and (v<=n) then update(u-1,v,d[u,v]+cot[u-1,v-1]); if (u>=1) and (u<=m) and (v>=2) and (v<=n) then update(u+1,v,d[u,v]+cot[u,v-1]); end; end; begin for i:=1 to 411 do for j:=1 to 411 do begin d[i,j]:=oo; hang[i,j]:=oo; cot[i,j]:=oo; end; read(m,n); for i:=1 to m do for j:=1 to n-1 do read(cot[i,j]); for i:=1 to m-1 do for j:=1 to n do read(hang[i,j]); for i:=1 to m+1 do begin d[i,n+1]:=0; push(i,n+1); end; res:=oo; ijk; for i:=1 to 411 do for j:=1 to 411 do d[i,j]:=oo; fillchar(hpos,sizeof(hpos),0); hsize:=0; for i:=1 to n+1 do begin d[1,i]:=0; push(1,i); end; ijk; if res=oo then res:=-1; writeln(res); end.
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; //typedef long double ld; typedef double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i) #define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i) #define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i) #define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) #define nl puts("") #define sp printf(" ") #define ok puts("ok") //#include <conio.h> template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} }; template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } const double PI = 2 * acos(0); const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"}; const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int dr[] = {0, 0, -1, +1}; const int dc[] = {-1, +1, 0, 0}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const double eps = ld(1e-9); const ll mod = 100000007; typedef pair<int, int> II; // Dinic #define maxn 405 #define maxe 1000005 int col[maxn][maxn], row[maxn][maxn]; ll f[maxn][maxn]; int n, m; priority_queue<pair<ll, II> > que; int main(){ // OPEN(); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); gi(n); gi(m); ms(f, 0x3f); Rep(i, n) Rep(j, m - 1) gi(col[i][j + 1]); Rep(i, n - 1) Rep(j, m) gi(row[i + 1][j]); if(n <= 1 && m <= 1){ printf("-1"); return 0; } For(j, 1, m - 1) { f[n][j] = 0; que.push(mp(0, mp(n, j))); } For(i, 1, n - 1){ f[i][0] = 0; que.push(mp(0, mp(i, 0))); } int r, c, u, v, rr, cc; ll cost, t; while(!que.empty()){ t = -que.top().fi; r = que.top().se.fi; c = que.top().se.se; que.pop(); if(f[r][c] < t) continue; if(r < n && c > 0 && c < m){ cost = t + col[r][c]; if(f[r + 1][c] > cost){ f[r + 1][c] = cost; que.push(mp(-cost, mp(r + 1, c))); } } if(r > 0 && c > 0 && c < m){ cost = t + col[r - 1][c]; if(f[r - 1][c] > cost){ f[r - 1][c] = cost; que.push(mp(-cost, mp(r - 1, c))); } } if(r > 0 && r < n && c < m){ cost = t + row[r][c]; if(f[r][c + 1] > cost){ f[r][c + 1] = cost; que.push(mp(-cost, mp(r, c + 1))); } } if(r > 0 && r < n && c > 0){ cost = t + row[r][c - 1]; if(f[r][c - 1] > cost){ f[r][c - 1] = cost; que.push(mp(-cost, mp(r, c - 1))); } } } ll res = linf; For(j, 1, m - 1) { res = min(res, f[0][j]); } For(i, 1, n - 1){ res = min(res, f[i][m]); } cout << res; }
Bình luận