bzoj2464: 中山市选[2009]小明的游戏(最短路)

2464: 中山市选[2009]小明的游戏

题目：传送门

---

题解：

　　 最短路的裸题...

　　

---

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 int dx[]={,,-,,};

 int dy[]={,,,-,};

 struct node

 {

     int x,y;

 }list[];

 int d[][],sx,sy,ex,ey;

 bool v[][];

 char s[][];

 int main()

 {

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         if(n== && m==)break;

         for(int i=;i<=n;i++)scanf("%s",s[i]+);

         scanf("%d%d%d%d",&sx,&sy,&ex,&ey);sx++;sy++;ex++;ey++;

         list[].x=sx;list[].y=sy;

         memset(d,,sizeof(d));d[sx][sy]=;

         memset(v,false,sizeof(v));v[sx][sy]=true;

         int head=,tail=;

         while(head!=tail)

         {

             int x=list[head].x,y=list[head].y;

             for(int i=;i<=;i++)

             {

                 int tx=x+dx[i],ty=y+dy[i];

                 if(tx< || ty< || tx>n || ty>m) continue;

                 int c;if(s[tx][ty]==s[x][y])c=;else c=;

                 if(d[tx][ty]>d[x][y]+c)

                 {

                     d[tx][ty]=d[x][y]+c;

                     if(v[tx][ty]==false)

                     {

                         v[tx][ty]=true;

                         list[tail].x=tx,list[tail].y=ty;

                         tail++;if(tail==n*m+)tail=;

                     }

                 }

             }

             head++;if(head==n*m+) head=;

             v[x][y]=false;

         }

         printf("%d\n",d[ex][ey]);

     }

     return ;

 }