Probleme de informatica - enunturi si rezolvari

Un labirint se codifica printr-o matrice nXm in care 0 sunt pozitii libere, iar -1 reprezinta zidurile. In pozitia io,jo se afla un soricel care se poate deplasa pe patru directii paralele cu liniile si coloanele matricii.
Afisati toate drumurile prin care soricelul poate parasi labirintul.
Exemplu:
5 7
-1 -1 0 -1 -1 -1 -1
0 0 0 0 0 0 0
-1 -1 -1 -1 -1 0 -1
-1 0 0 0 0 0 0
-1 -1 -1 -1 -1 -1 -1
4 2
O solutie este:
-1 -1 0 -1 -1 -1 -1
0 0 0 0 0 7 8
-1 -1 -1 -1 -1 6 -1
-1 1 2 3 4 5 0
-1 -1 -1 -1 -1 -1 -1
4,2 4,3 4,4 4,5 4,6 3,6 2,6 2,7

#include<fstream>
#include<iomanip>
using namespace std;
  fstream f("date.in", ios::in);
  fstream g("date.out",ios::out);

  int a[100][100],n,io,jo,b[100][3],m;
  int di[8]={0,0,-1,1};
  int dj[8]={-1,1,0,0};

  int inside(int i,int j)
      { return i>=1 && j>=1 && i<=n && j<=m;
      }
	  
  void citire()
     { f>>n>>m;
       for(int i=1;i<=n;i++)
	     for(int j=1;j<=m;j++)
	       f>>a[i][j];
	 f>>io>>jo;
     }

  void afis(int k)
    { for(int i=1;i<=n;i++)
	{  g<<endl;
	     for(int j=1;j<=m;j++)
	       g<<setw(3)<<a[i][j];
	}
     g<<endl;
     for(int i=0;i<=k; i++)
     g<<b[i][1]<<","<<b[i][2]<<"  ";
     g<<endl;
   }
	
 int sol(int i,int j)
 {
	 return i==1 || j==1 || i==n || j==m;
 }

 void back(int i,int j,int k)
   { if(sol(i,j)) afis(k-1);
	else for(int p=0;p<=3;p++)
		{int inou,jnou;
		 inou=i+di[p];
		 jnou=j+dj[p];
		 if(inside(inou,jnou) && a[inou][jnou]==0)
		     {
		       b[k][1]=inou;
		       b[k][2]=jnou;
		       a[inou][jnou]=k+1;
			   back(inou,jnou,k+1);
			   a[inou][jnou]=0;
			 }
		     
		}
   }
 int main()
   { citire();
     a[io][jo]=1;
     b[0][1]=io;
     b[0][2]=jo;
     back(io,jo,1);
	 return 0;
   }

19 apr 2024

Site-ul conține 884 de probleme rezolvate