记录编号	302087	评测结果	AA
题目名称	最少转弯问题	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-09-03 10:41:32	内存使用	10.37 MiB

#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstdlib>
#define LL long long
using namespace std;
const int maxn=1010;
struct Node{
    int x,y,type,step;//type==0为横向，type==1为纵向 
    Node(){};
    Node(int a,int b,int c,int d){x=a;y=b;step=c;type=d;}
};
queue<Node> q;
int n,m,bx,by,ex,ey;
int ans=0x7f7f7f7f;
bool a[maxn][maxn];
int vis[maxn][maxn][5];
void Init();
void Bfs(){
    q.push(Node(ex,ey,0,0));vis[ex][ey][0]=1;
    q.push(Node(ex,ey,0,1));vis[ex][ey][1]=1;
    while(!q.empty()){
        Node temp=q.front();q.pop();
        //printf("炸死壁垒！\n");
        int x=temp.x,y=temp.y,step=temp.step,type=temp.type;
        if(x==bx && y==by){ans=min(ans,step);}
        if(type==0){//横向 
            if((!vis[x][y-1][type] || vis[x][y-1][type]>step+1) && !a[x][y-1] && y-1>=1){vis[x][y-1][type]=step+1;q.push(Node(x,y-1,step,type));} 
            if((!vis[x][y+1][type] || vis[x][y+1][type]>step+1) && !a[x][y+1] && y+1<=n){vis[x][y+1][type]=step+1;q.push(Node(x,y+1,step,type));}
            type=1;
            if((!vis[x-1][y][type] || vis[x-1][y][type]>step+2) && !a[x-1][y] && x-1>=1){vis[x-1][y][type]=step+2;q.push(Node(x-1,y,step+1,type));}
            if((!vis[x+1][y][type] || vis[x+1][y][type]>step+2) && !a[x+1][y] && x+1<=n){vis[x+1][y][type]=step+2;q.push(Node(x+1,y,step+1,type));}
        }
        else {//纵向 
            if((!vis[x-1][y][type] || vis[x-1][y][type]>step+1) && !a[x-1][y] && x-1>=1){vis[x-1][y][type]=step+1;q.push(Node(x-1,y,step,type));}
            if((!vis[x+1][y][type] || vis[x+1][y][type]>step+1) && !a[x+1][y] && x+1<=n){vis[x+1][y][type]=step+1;q.push(Node(x+1,y,step,type));}
            type=0;
            if((!vis[x][y-1][type] || vis[x][y-1][type]>step+2) && !a[x][y-1] && y-1>=1){vis[x][y-1][type]=step+2;q.push(Node(x,y-1,step+1,type));}
            if((!vis[x][y+1][type] || vis[x][y+1][type]>step+2) && !a[x][y+1] && y+1<=n){vis[x][y+1][type]=step+2;q.push(Node(x,y+1,step+1,type));}
        }
    }
}
int main(){
    freopen("turn.in","r",stdin);freopen("turn.out","w",stdout);
    Init();
    //system("pause");
    return 0;
} 
void Init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    scanf("%d%d%d%d",&bx,&by,&ex,&ey);
    //for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%d",a[i][j]);} printf("\n");} 
    Bfs();
    printf("%d\n",ans);
}
/*
5 7
1 0 0 0 0 1 0
0 0 1 0 1 0 0
0 0 0 0 1 0 1
0 1 1 0 0 0 0
0 0 0 0 1 1 0
1 3 1 7
ans=6
*/