Pagini recente » Cod sursa (job #628669) | Cod sursa (job #914339) | Cod sursa (job #1104892) | Cod sursa (job #384646) | Cod sursa (job #2296555)
#include <bits/stdc++.h>
#define Dim 505
#define Max 1000009
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int N,M,C[Dim][Dim],Si,Sj,Fi,Fj;
int Ans[Dim][Dim],info;
int dx[]={0,-1,1,0,0,-1,-1,1,1},dy[]={0,0,0,-1,1,-1,1,-1,1};
stack < pair < int,int > > stv;
bool stop=0;
int OK(int coordx,int coordy)
{
if(coordx<=N&&coordy<=M&&coordx>=1&&coordy>=1&&C[coordx][coordy]==0)
return 1;
else return 0;
}
int Go(int nr1,int nr2)
{
int input1=stv.top().first;
int input2=stv.top().second;
if(nr1==-1&&nr2==-1)
{
if(input1==-1&&input2==-1)return 0;
else if(input1==1&&input2==1) return 4;
else if(input1==-1&&input2==1) return 2;
else if(input1==1&&input2==-1) return 2;
else if(input1==-1&&input2==0) return 1;
else if(input1==1&&input2==0) return 3;
else if(input1==0&&input2==-1) return 1;
else if(input1==0&&input2==1) return 3;
}
if(nr1==-1&&nr2==0)
{
if(input1==-1&&input2==-1)return 1;
else if(input1==1&&input2==1) return 3;
else if(input1==-1&&input2==1) return 1;
else if(input1==1&&input2==-1) return 3;
else if(input1==-1&&input2==0) return 0;
else if(input1==1&&input2==0) return 4;
else if(input1==0&&input2==-1) return 2;
else if(input1==0&&input2==1) return 2;
}
if(nr1==-1&&nr2==1)
{
if(input1==-1&&input2==-1)return 2;
else if(input1==1&&input2==1) return 2;
else if(input1==-1&&input2==1) return 0;
else if(input1==1&&input2==-1) return 4;
else if(input1==-1&&input2==0) return 1;
else if(input1==1&&input2==0) return 3;
else if(input1==0&&input2==-1) return 3;
else if(input1==0&&input2==1) return 1;
}
if(nr1==0&&nr2==-1)
{
if(input1==-1&&input2==-1)return 1;
else if(input1==1&&input2==1) return 3;
else if(input1==-1&&input2==1) return 3;
else if(input1==1&&input2==-1) return 1;
else if(input1==-1&&input2==0) return 2;
else if(input1==1&&input2==0) return 2;
else if(input1==0&&input2==-1) return 0;
else if(input1==0&&input2==1) return 4;
}
if(nr1==0&&nr2==1)
{
if(input1==-1&&input2==-1)return 3;
else if(input1==1&&input2==1) return 1;
else if(input1==-1&&input2==1) return 1;
else if(input1==1&&input2==-1) return 3;
else if(input1==-1&&input2==0) return 2;
else if(input1==1&&input2==0) return 2;
else if(input1==0&&input2==-1) return 4;
else if(input1==0&&input2==1) return 0;
}
if(nr1==1&&nr2==1)
{
if(input1==-1&&input2==-1)return 4;
else if(input1==1&&input2==1) return 0;
else if(input1==-1&&input2==1) return 2;
else if(input1==1&&input2==-1) return 2;
else if(input1==-1&&input2==0) return 3;
else if(input1==1&&input2==0) return 1;
else if(input1==0&&input2==-1) return 3;
else if(input1==0&&input2==1) return 1;
}
if(nr1==1&&nr2==0)
{
if(input1==-1&&input2==-1)return 3;
else if(input1==1&&input2==1) return 1;
else if(input1==-1&&input2==1) return 3;
else if(input1==1&&input2==-1) return 1;
else if(input1==-1&&input2==0) return 4;
else if(input1==1&&input2==0) return 0;
else if(input1==0&&input2==-1) return 2;
else if(input1==0&&input2==1) return 2;
}
if(nr1==1&&nr2==-1)
{
if(input1==-1&&input2==-1)return 2;
else if(input1==1&&input2==1) return 2;
else if(input1==-1&&input2==1) return 4;
else if(input1==1&&input2==-1) return 0;
else if(input1==-1&&input2==0) return 3;
else if(input1==1&&input2==0) return 1;
else if(input1==0&&input2==-1) return 3;
else if(input1==0&&input2==1) return 1;
}
}
void DFS(int x,int y,int mod1,int mod2)
{
int l=x+mod1;
int c=y+mod2;
//cout<<x<<" "<<y<<" "<<C[x][y]<<" "<<l<<" "<<c<<" "<<C[l][c]<<'\n';
if(OK(l,c))
{
info=Go(mod1,mod2);
if(Ans[x][y]+info>=Ans[l][c]) return;
else
{
Ans[l][c]=Ans[x][y]+info;
//cout<<l<<" "<<c<<" "<<info<<" "<<Ans[x][y]<<" "<<Ans[l][c]<<'\n';;
stv.push(make_pair(mod1,mod2));
}
}else return;
for(int i=1;i<=8;i++)
DFS(l,c,dx[i],dy[i]);
stv.pop();
}
int main()
{
f>>N>>M>>Si>>Sj>>Fi>>Fj;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
{
f>>C[i][j];
Ans[i][j]=Max;
}
Ans[Si][Sj]=0;
if(Si==Fi&&Sj==Fj)
{
g<<0;
stop=1;
}
else
{
for(int i=1;i<=8;i++)
{
stv.push(make_pair(dx[i],dy[i]));
DFS(Si,Sj,dx[i],dy[i]);
}
g<<Ans[Fi][Fj];
}
return 0;
}