Titlul: inginer/problema de la .campion Scris de: Sven-Alexander Gal din Martie 29, 2014, 17:58:15 Știe cineva o rezolvare mai eficientă a problemei Inginer. Eu ma incercat așa(folosinf algoritmul lui Lee):
#include<fstream> using namespace std; ifstream f("inginer.in"); ofstream g("inginer.out"); struct Pozitie{int lin,col;}; void lee(int n,int m,int l[78][78],int stx,int sty,int spx, int spy) { struct Pozitie C[n*m]; Pozitie ps,pc,p,v; int i; //Bordura cu 0 for(i=0; i<=m; i++) l[0] = 0,l[n+1] = 0; for(i=0; i<=n; i++) l
ps.lin = stx; // Poz de start ps.col = sty; pc.lin = spx; // Poz de final pc.col = spy; int prim=0,ultim=0; l[ps.lin][ps.col] = 1; // Marcam pozitia de start si de final l[pc.lin][pc.col] = 0; int dc[]={0,1,0,-1}; int dl[]={-1,0,1,0}; int dist=0; C[0] = ps; // Pozitia de start while(prim <= ultim && l[pc.lin][pc.col] == 0) { dist++; p = C[prim]; prim++; for(i=0; i<4; i++) { v.lin = p.lin + dl; v.col = p.col + dc; if(v.lin >= 1 && v.lin <= n+1 && v.col >= 1 && v.col<=m+1) if(l[v.lin][v.col] == 0) { l[v.lin][v.col] = dist; ultim++; C[ultim] = v; } } } if(l[pc.lin][pc.col] == 0) g<<"0\n"; else g<<dist<<"\n"; } int main() { int i,j,n,m,l[78][78]; char x; int x1,y1,x2,y2; f>>n>>m; for(i=1; i<=n; i++) for(j=1; j<=m; j++) { f>>x; if(x == 'X') l[j] = -1; // zid else l[j] = 0; //culoar } do{ f>>x1; f>>y1; f>>x2; f>>y2; if(x1 != 0 && x2 != 0 && y1 != 0 && y2 != 0) lee(n,m,l,x1,y1,x2,y2); } while(x1 != 0 && x2 != 0 && y1 != 0 && y2 != 0); f.close(); g.close(); return 0; } Titlul: Răspuns: inginer/problema de la .campion Scris de: Puscas Sergiu din Mai 03, 2014, 10:29:32 Se poate lua 100 cu Lee. Din ceva motiv, primesc eroare de compilare pe sursa ta (incepand cu eroare la linia l[0] = 0, l[n+1] = 0, unde l e tablou bidimensional). Iti atasez sursa mea, in caz ca te ajuta:
Cod: #include <iostream> Titlul: Răspuns: inginer/problema de la .campion Scris de: Borozan Ionut din August 17, 2015, 11:29:22 Buna ziua.Am si eu o problema.Ma puteti ajuta?Caci nu stiu de ce nu obtin punctaj.
#include <fstream> # include <queue> using namespace std; ifstream f1("inginer.in"); ofstream f2("inginer.out"); struct punct {int l,c;}p,pnou; queue <punct> coada; int A[50][50],i,n,m,x1,x2,y1,y2,j; int dl[]={-1,0,1,0},dc[]={0,1,0,-1}; char x; void citeste() { f1>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { f1>>x; if(x=='X') A[j]=-1; else A[j]=0; } //bordam cu 0; for(i=1;i<=n;i++) A[0]=A[n+1]=A
} void lee() {f1>>x1>>y1>>x2>>y2;p.l=x1;p.c=y1;A[p.l][p.c]=1; A[x2][y2]=0; coada.push(p); A[x1][y1]=1; punct pnou; while(!coada.empty() && A[x2][y2]==0) { p=coada.front(); coada.pop(); for(i=0;i<4;i++) {pnou.l=p.l+dl; pnou.c=p.c+dc; if(A[pnou.l][pnou.c]==0) { coada.push(pnou); A[pnou.l][pnou.c]=A[p.l][p.c]+1; } } } f2<<A[x2][y2]; } int main() {citeste(); while(x1!=0 && y1!=0 && x2!=0 && y2!=0); { lee(); } f1.close();f2.close(); return 0; } |