Pagini recente » Cod sursa (job #720184) | Cod sursa (job #2141028) | Cod sursa (job #1960655) | Cod sursa (job #2282218) | Cod sursa (job #2309158)
#include <fstream>
#include <deque>
using namespace std;
ifstream f("rover.in");
ofstream g("rover.out");
const int dx[]={0,-1,0,1};
const int dy[]={-1,0,1,0};
int n,c,mat[501][501],nr;
int a[501][501];
void afisarea(){
int i,j;
for(i=1; i<=n; i++){
for(j=1; j<=n; j++)
g<<a[i][j]<<" ";
g<<"\n";
}
}
void afisaremat(){
int i,j;
for(i=1; i<=n; i++){
for(j=1; j<=n; j++)
g<<mat[i][j]<<" ";
g<<"\n";
}
}
void fills(int x, int y){
mat[x][y]=-1;
int i;
for(i=0; i<4; i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(!mat[nx][ny])
fills(nx, ny);
}
}
void Lee(){
int nx,ny,i,x,y;
deque<int> qx, qy, qqx, qqy;
if(a[1][1]==1){
qqx.push_back(1);
qqy.push_back(1);
}
else{
qx.push_back(1);
qy.push_back(1);}
mat[1][1]=1;
qqx.push_back(-1);
while(!qqx.empty()){
if(qqx.back()==-1)
qqx.pop_back();
while(!qqx.empty()){
qx.push_back(qqx.front());
qy.push_back(qqy.front());
qqx.pop_front();
qqy.pop_front();
}
while(!qx.empty()){
x=qx.front();
y=qy.front();
qx.pop_front();
qy.pop_front();
for(i=0; i<4; i++){
nx=x+dx[i];
ny=y+dy[i];
if(!mat[nx][ny] && !a[nx][ny]){
qx.push_back(nx);
qy.push_back(ny);
mat[nx][ny]=mat[x][y]+1;
}
else
if(!mat[nx][ny]){
qqx.push_back(nx);
qqy.push_back(ny);
mat[nx][ny]=mat[x][y]+2;
}
}
}
}
}
void rezolvare1(){
int i,j,x;
f>>n>>c;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++){
f>>x;
if(x<c)
a[i][j]=0;
else
a[i][j]=1;
mat[i][j]=a[i][j];
}
for(i=0; i<=n+1; i++)
a[i][0]=a[0][i]=a[i][n+1]=a[n+1][i]= mat[i][0]=mat[0][i]=mat[i][n+1]=mat[n+1][i]=-1;
if(!a[1][1] && !a[n][n]){
fills(1,1);
if(mat[n][n]==-1)
g<<0;
else{
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
mat[i][j]=0;
Lee();
// afisaremat();
i=j=n;
while(i!=1 || j!=1){
bool ok=0;
int nx,ny;
for(int o=0; o<4 && !ok; o++){
nx=i+dx[o];
ny=j+dy[o];
if(mat[nx][ny]==mat[i][j]-1)
{
// g<<i<<" "<<j<<" "<<nx<<" "<<ny<<"\n";
// g<<mat[i][j]<<" "<<mat[nx][ny]<<"\n";
i=nx;
j=ny;
ok=1;
}
}
if(!ok){
ok=0;
for(int o=0; o<4 && !ok; o++){
nx=i+dx[o];
ny=j+dy[o];
if(mat[nx][ny]==mat[i][j]-2)
{
nr++;
i=nx;
j=ny;
ok=1;
}
}
}
if(!ok)
i=j=n;
}
g<<nr;
// g<<"\n"<<mat[4][2]<<" "<<mat[4][1];
}
}
else{
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
mat[i][j]=0;
Lee();
// afisarea();
// afisaremat();
i=j=n;
while(i!=1 || j!=1){
bool ok=0;
int nx,ny;
for(int o=0; o<4 && !ok; o++){
nx=i+dx[o];
ny=j+dy[o];
if(mat[nx][ny]==mat[i][j]-1)
{
// g<<i<<" "<<j<<" "<<nx<<" "<<ny<<"\n";
// g<<mat[i][j]<<" "<<mat[nx][ny]<<"\n";
i=nx;
j=ny;
ok=1;
}
}
if(!ok){
ok=0;
for(int o=0; o<4 && !ok; o++){
nx=i+dx[o];
ny=j+dy[o];
if(mat[nx][ny]==mat[i][j]-2)
{
nr++;
i=nx;
j=ny;
ok=1;
}
}
}
if(!ok)
i=j=n;
}
if(a[n][n])
nr++;
g<<nr;
}
//afisaremat();
}
int main(){
int p;
f>>p;
if(p==1)
rezolvare1();
else
g<<2;
return 0;
}