InfoAs Atlas

<- Go back View preview

Problema Labirint

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

Un labirint este descris ca fiind o matrice binară cu `N` linii și `M` coloane, cu semnificația că `0` reprezintă o poziție liberă, iar `1` reprezintă o poziție în care se află un zid. Un drum în labirint este un traseu în matrice care începe cu poziția `(1, 1)` și ajunge în poziția `(N, M)` prin deplasare doar pe poziții care au valoarea `0` și sunt vecine cu poziția curentă, pe una din cele patru direcții: sus, jos, stânga, dreapta. Lungimea unui drum este egală cu numărul de poziții vizitate. 
 
Notăm cu `d0` lungimea drumului minim de la poziția `(1, 1)` la poziția `(N, M)`. Fie `d(i, j)` lungimea drumului minim de la poziția `(1, 1)` la poziția `(N, M)`, dacă poziției `(i, j)` i se atribuie valoarea `0`. Observăm că dacă poziția `(i, j)` conține inițial un `0`, atunci `d0 = d(i,j)`.

## Cerință

Pentru fiecare poziție `(i, j)`, să se verifice dacă `d(i, j) < d0`.
## Date de intrare

Pe prima linie a fișierului `labirint.in` se află două numere naturale `N` și `M`, dimensiunile matricei binare ce descrie labirintul, apoi pe următoarele `N` linii se vor afla câte `M` valori binare, ce reprezintă elementele matricei care descrie labirintul, neseparate prin spații.
## Date de ieșire

În fișierul `labirint.out` se vor scrie `N` linii, iar pe fiecare linie se vor scrie `M` cifre, neseparate prin spații. Cifra a `j`-a de pe linia a `i`-a este `1` dacă și numai dacă `d(i, j) < d0`, altfel este `0`.
## Restricții și precizări

* `1 ≤ N ≤ 1000`
  * `1 ≤ M ≤ 1000`
  * Pe pozițiile `(1, 1)` și `(N, M)` se vor afla valori `0`
  * Se garantează că există un drum în matricea inițială între pozițiile `(1, 1)` și `(N, M)`

### Pentru 10 puncte

* `1 ≤ N ≤ 50`
 * `1 ≤ M ≤ 50`
 * `d0 = N + M - 1`

### Pentru alte 30 puncte

* `1 ≤ N ≤ 50`
  * `1 ≤ M ≤ 50`

### Pentru alte 60 de puncte

* Fără alte restricții

Examples

Default code

Summary

Editorial

_Descriere oferită de propunători._

_Propunător: prof. Gheorghe Manolache, stud. Ștefan-Cosmin Dăscălescu_

Mai întâi vom afla, folosind algoritmul lui Lee, distanța minimă de la `(1, 1)` la `(N, M)`, notată în enunț cu `d0`. Acum, diferența dintre soluția optimă și soluția parțială va consta în modul în care verificăm pentru fiecare poziție egală cu `1` dacă distanța se modifică.

**Soluție pentru 10 puncte.** Pentru primul grup de teste, deoarece `d0 = N + M - 1`, se poate observa că nu va exista nicio zonă care să îmbunătățească răspunsul, deci se poate obține punctajul pe aceste teste afișând o matrice numai cu valori egale cu `0`.

**Soluție pentru 40 de puncte.** Pentru cel de-al doilea grup de teste, se poate simula cu ajutorul algoritmului lui Lee înlocuirea fiecărei valori egale cu `1` și se va verifica dacă distanța de la `(1, 1)` la `(N, M)` s-a micșorat, afișându-se `1` sau `0`, după caz, complexitatea acestui algoritm fiind `O(N2M2)`.

De notat că această soluție rezolvă corect și testele din primul grup 1.

**Soluție pentru 100 de puncte.** Pentru a ajunge la soluția optimă, se va observa faptul că nu e nevoie să rulăm algoritmul lui Lee de fiecare dată când modificăm valoarea unei poziții, fiind de ajuns precalcularea distanțelor atât din `(1, 1)` cât și din `(N, M)` către toate celelalte poziții din matrice. Astfel, pentru fiecare zonă `(i, j)` în care se poate ajunge atât din `(1, 1)`, cât și din `(N, M)`, distanța pe care o vom avea de la `(1, 1)` la `(N, M)` trecând printr-o poziție `(i, j)` egală inițial cu `1` va fi egală cu următoarea valoare: `d(i, j) = dist1(i, j) + dist2(i,j) - 1`, unde `dist1(i, j)` reprezintă distanța de la `(1, 1)` la `(i, j)`, iar `dist2(i, j)` reprezintă distanța de la `(N, M)` la `(i, j)`, fiind necesară scăderea lui `1` deoarece poziția `(i, j)` apare în ambele distanțe.

Complexitatea algoritmului pentru soluția ce obține 100 de puncte devine astfel `O(NM)`.

Solution

```
/*
Sursa preluata de pe InfoArena,
https://infoarena.ro/job_detail/2722380?action=view-source,
sub licenta CC BY-NC 2.5.
*/

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
//const int MOD=100003;
ifstream f("labirint.in");
ofstream g("labirint.out");
int n,m;
char s[1005][1005];
int dist1[1005][1005],dist2[1005][1005];
int dx[4]= {0,1,0,-1};
int dy[4]= {1,0,-1,0};
void lee()
{
 queue<pair<int,int> > q;
 q.push({1,1});
 dist1[1][1]=1;
 while(!q.empty())
 {
 int x=q.front().first;
 int y=q.front().second;
 for(int d=0; d<4; d++)
 {
 int xx=x+dx[d];
 int yy=y+dy[d];
 if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&dist1[xx][yy]>dist1[x][y]+1)
 {
 dist1[xx][yy]=dist1[x][y]+1;
 if(s[xx][yy]=='0')
 {
 q.push({xx,yy});
 }
 }
 }
 q.pop();
 
 }
 
}
void lee2()
{
 queue<pair<int,int> > q;
 q.push({n,m});
 dist2[n][m]=1;
 while(!q.empty())
 {
 int x=q.front().first;
 int y=q.front().second;
 for(int d=0; d<4; d++)
 {
 int xx=x+dx[d];
 int yy=y+dy[d];
 if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&dist2[xx][yy]>dist2[x][y]+1)
 {
 dist2[xx][yy]=dist2[x][y]+1;
 if(s[xx][yy]=='0')
 {
 q.push({xx,yy});
 }
 }
 }
 q.pop();
 
 }
}
int main()
{
 f>>n>>m;
 for(int i=1; i<=n; i++)
 {
 f>>(s[i]+1);
 }
 for(int i=1; i<=n; i++)
 {
 for(int j=1; j<=m; j++)
 {
 dist1[i][j]=dist2[i][j]=1000000;
 }
 }
 lee();
 lee2();
 for(int i=1;i<=n;i++)
 {
 for(int j=1;j<=m;j++)
 {
 if(dist1[i][j]+dist2[i][j]-1<dist1[n][m]&&s[i][j]=='1')
 {
 g<<1;
 
 }
 else g<<0;
 
 }
 
 g<<'\n';
 }
}
```

Contributor ID

Author

Tags

Problem set

Chapter ID

Published At

Admin Approved

Difficulty

License

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	3 KB	View
0-labirint.in	/ 100	10 January 2025 21:26	512 B	View
0-labirint.ok	/ 100	10 January 2025 21:26	506 B	View
1-labirint.in	/ 100	10 January 2025 21:26	1 KB	View
1-labirint.ok	/ 100	10 January 2025 21:26	1 KB	View
2-labirint.in	/ 100	10 January 2025 21:26	231 B	View
2-labirint.ok	/ 100	10 January 2025 21:26	225 B	View
3-labirint.in	/ 100	10 January 2025 21:26	1 KB	View
3-labirint.ok	/ 100	10 January 2025 21:26	1 KB	View
4-labirint.in	/ 100	10 January 2025 21:26	996 B	View
4-labirint.ok	/ 100	10 January 2025 21:26	990 B	View
5-labirint.in	/ 100	10 January 2025 21:26	974 B	View
5-labirint.ok	/ 100	10 January 2025 21:26	968 B	View
6-labirint.in	/ 100	10 January 2025 21:26	2 KB	View
6-labirint.ok	/ 100	10 January 2025 21:26	2 KB	View
7-labirint.in	/ 100	10 January 2025 21:26	2 KB	View
7-labirint.ok	/ 100	10 January 2025 21:26	2 KB	View
8-labirint.in	/ 100	10 January 2025 21:26	8 KB	View
8-labirint.ok	/ 100	10 January 2025 21:26	8 KB	View
9-labirint.in	/ 100	10 January 2025 21:26	25 KB	View
9-labirint.ok	/ 100	10 January 2025 21:26	25 KB	View
10-labirint.in	/ 100	10 January 2025 21:26	39 KB	View
10-labirint.ok	/ 100	10 January 2025 21:26	39 KB	View
11-labirint.in	/ 100	10 January 2025 21:26	76 KB	View
11-labirint.ok	/ 100	10 January 2025 21:26	76 KB	View
12-labirint.in	/ 100	10 January 2025 21:26	117 KB	View
12-labirint.ok	/ 100	10 January 2025 21:26	117 KB	View
13-labirint.in	/ 100	10 January 2025 21:26	156 KB	View
13-labirint.ok	/ 100	10 January 2025 21:26	156 KB	View
14-labirint.in	/ 100	10 January 2025 21:26	245 KB	View
14-labirint.ok	/ 100	10 January 2025 21:26	245 KB	View
15-labirint.in	/ 100	10 January 2025 21:26	348 KB	View
15-labirint.ok	/ 100	10 January 2025 21:26	348 KB	View
16-labirint.in	/ 100	10 January 2025 21:26	477 KB	View
16-labirint.ok	/ 100	10 January 2025 21:26	477 KB	View
17-labirint.in	/ 100	10 January 2025 21:26	623 KB	View
17-labirint.ok	/ 100	10 January 2025 21:26	623 KB	View
18-labirint.in	/ 100	10 January 2025 21:26	803 KB	View
18-labirint.ok	/ 100	10 January 2025 21:26	803 KB	View
19-labirint.in	/ 100	10 January 2025 21:26	977 KB	View
19-labirint.ok	/ 100	10 January 2025 21:26	977 KB	View
In total: 42 files 7 MB

View files grouped by their test cases.

Index	Input file	Output file	Score	Visibility

Enzo Judge

Offline

Server is offline.

Fernando Judge

Offline

Server is offline.

Main Instance

Offline

Server is offline.

Judge count: 2 Instance count: 1

Online judges will be synchronised with all the files. The previous version(s) of the problem will be overwritten.

Problema Labirint

Identification properties

Content properties

Technical properties

Delete all files