BFS, zadanie

Dla testów z zadania działa poprawnie?

szweszwe napisał(a):

Dla testów z zadania działa poprawnie?
Tak

To, że w dokumencie jest co innego niż u ciebie na wyjściu to nie przeszkadza?

szweszwe napisał(a):

To, że w dokumencie jest co innego niż u ciebie na wyjściu to nie przeszkadza?
Poproszę jaśniej.
Gdzie jest co innego ?
Jeśli chodzi o brakujące D to nie ma znaczenia, w treści zadania jest to opisane.

pattom napisał(a):

Cześć,

mam takie zadanie:
http://solve.edu.pl/contests/download_desc/2056
i taki kod:
https://wandbox.org/permlink/7BmvYCPLf0G4ohuK

dla testów z zadania działa poprawnie ale nie wiem czemu dla innych nie:-(

Błąd w treści.

A nie powinieneś podać
1 3
S.W
?
Bo to pole ma wymiar 3.

szweszwe napisał(a):

A nie powinieneś podać
1 3
S.W
?
Bo to pole ma wymiar 3.

Tak oczywiście, test działa.
Dlatego pisałem o błędzie w treści maila ale nie mogłem edytować.
Ale mimo to nie przechodzi wszystkich testów na sprawdzaczce :-(

A co powinno być w takim przypadku?
1 1
W

szweszwe napisał(a):

A co powinno być w takim przypadku?
1 1
W

Teoretycznie pewnie powinnop wypisać Tak, bo jak nie ma owiec to wilk nie ma co zjadać więc owce są chronione :-)

Zastanawiam się po co tam BFS?
Psy są nielimitowane.
Już podczas wczytywania danych można zamienić wszystkie '.' na 'D' a potem tylko sprawdzić czy 'S' nie sąsiaduje z 'W'.
BFS nie przyspieszy ani nie ułatwi algorytmu.

Proponowałbym tak:

#include <iostream>
using namespace std;

char T[505][505]; //tworzenie tablicy globalnej

int main() {
	int W, K;
	cin>>W>>K;
	char A[K];
	for(int i=1;i<=W;i++){//wczytanie tablicy numeracja od 1
		cin>>A+1;
		for(int j=1;j<=K;j++){
			T[i][j]=A[j];
		}
	}
	for(int i=1;i<=W;i++){
		for(int j=1;j<=K;j++){
			if(T[i][j]=='W'){
				if(T[i-1][j]=='S' || T[i+1][j]=='S' || T[i][j+1]=='S' || T[i][j-1]=='S'){//jesli owca koło wilka to się nie da postawić psa
					cout<<"Nie";
					return 0;
				} else{ //w przeciwnym wypadku otaczamy wilka psami
					T[i-1][j]='D';
					T[i+1][j]='D';
					T[i][j+1]='D';
					T[i][j-1]='D';
				}
			}
		}
	}
	cout<<"Tak\n";
	for(int i=1;i<=W;i++){//wypisanie tablicy
		for(int j=1;j<=K;j++){
			cout<<T[i][j];
		}
		cout<<endl;
	}
	return 0;
}

Jeśli koło wilka jest owca to nie da się postawić psa w przeciwnym wypadku można wilka otoczyć psami.

1. Tablica o wielkości 502x502 powinna wystarczyć.
   10-15) Na brzegach tablicy zostają przypadkowe wartości.
   22-27) Sąsiadujące wilki zostaną zastąpione psami.