P4554 小明的游戏
题面
题目描述
小明最近喜欢玩一个游戏。给定一个的棋盘，上面有两种格子#和@。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是，否则费用是。请编程计算从起始位置移动到目标位置的最小花费。
输入格式
输入文件有多组数据。
输入第一行包含两个整数，，分别表示棋盘的行数和列数。
输入接下来的行，每一行有个格子（使用#或者@表示）。
输入接下来一行有四个整数，分别为起始位置和目标位置。
当输入，均为时，表示输入结束。
输出格式
对于每组数据，输出从起始位置到目标位置的最小花费。每一组数据独占一行。
样例 #1
样例输入 #1
2 2
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0
0 0样例输出 #1
2
0提示
对于20%的数据满足：。
对于40%的数据满足：。
对于100%的数据满足：。
思路
二维图？最短路？
先直接转成一维的，这里可以用编号转换也可以读入的时候记录一下。
这道题数据范围也不是很大，出题人也没有去卡某种已经死掉的算法，所以其实这道题有三种做法。
其一，直接跑 Dijkstra 或者 SPFA 。两种做法都能过掉甚至 SPFA 跑得还更快一些。
其二，这种边权只有0和1的图可以用双端队列优化，理由如下：
若采用优先队列，未免很浪费资源，因为插入操作的复杂度是，但是如果换为双端队列的话，就可以变为。
遇到0就放在队首，遇到1就放到队尾，因为遇到0最短路距离不会变大，相对更优，要优先遍历。
代码
三种方式的代码我都写了，下面是带有海量注释的代码。
#include<bits/stdc++.h>
using namespace std;
// const int N=251000;
const int M=520300;
char e[515][515];//
int sum[515][515];
int dist[M];//
int fir[M];//
int n,m,cnt,ct;//
bool righ[M];//
int x_1,x_2,y_1,y_2;
struct edge
{
int to,nxt,val;
}ed[M];
struct point{
int p,d;//原点到p的最短距离为d
point(){}
point(int a,int b){p=a;d=b;}
bool operator<(const point &a)const
{
return a.d<d;
}
};
void add(int u,int v,int w)
{
ed[++cnt].to=v;
ed[cnt].val=w;
ed[cnt].nxt=fir[u];
fir[u]=cnt;
}
// bool operator<(const point &a,const point &b)//STL默认大根堆，上面是大的
// {
// return a.d>b.d;//小根堆
// }
// priority_queue<point> heap;
// void Dijkstra(int x)
// {
// while(heap.size()) heap.pop();
// for(int i=1;i<=n*m;i++)
// {
// dist[i]=INT_MAX;
// righ[i]=false;
// }
// // memset(dist,0x3f,sizeof(dist));
// dist[x]=0;
// for(int i=1;i<=n*m;i++)
// heap.push(point(i,dist[i]));
// for(int i=1;i<=n*m;i++)
// {
// while(righ[heap.top().p]) heap.pop();
// point now=heap.top();
// heap.pop();
// int pp=now.p;
// righ[pp]=true;
// for(int j=fir[pp];j;j=ed[j].nxt)
// {
// int v=ed[j].to;
// int dis=dist[pp]+ed[j].val;
// if(dist[v]>dis)
// {
// dist[v]=dis;
// heap.push(point(v,dist[v]));
// }
// }
// }
// }
// deque<int> q;
// void SPFA(int x)
// {
// for(int i=1;i<=ct;i++)
// {
// dist[i]=INT_MAX;
// righ[i]=false;
// }
// dist[x]=0;
// righ[x]=true;
// q.push_back(x);
// while(!q.empty())
// {
// int now=q.front();
// q.pop_front();
// righ[now]=false;
// for(int i=fir[now];i;i=ed[i].nxt)
// {
// int v=ed[i].to;
// if(dist[v]>dist[now]+ed[i].val)
// {
// dist[v]=dist[now]+ed[i].val;
// if(!righ[v])
// {
// righ[v]=true;
// if(!q.empty()&&dist[q.front()]<dist[v]) q.push_back(v);//队列不空防止RE，小的就放在队头，大的就放在队尾
// else q.push_front(v);
// }
// }
// }
// }
// }
queue<int> q;
void SPFA(int x)
{
for(int i=1;i<=ct;i++)
{
dist[i]=INT_MAX;
righ[i]=false;
}
dist[x]=0;
righ[x]=true;
q.push(x);
while(!q.empty())
{
int now=q.front();
q.pop();
righ[now]=false;
for(int i=fir[now];i;i=ed[i].nxt)
{
int v=ed[i].to;
if(dist[v]>dist[now]+ed[i].val)
{
dist[v]=dist[now]+ed[i].val;
if(!righ[v])
{
righ[v]=true;
q.push(v);
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m))
{
// getchar();//换行
if(n==0&&m==0) break;
memset(fir,0,sizeof(fir));
memset(sum,0,sizeof(sum));
// memset(e,0,sizeof(e));
for(int i=1;i<=cnt;i++)
{
ed[i].to=0;
ed[i].val=0;
ed[i].nxt=0;
}
cnt=0,ct=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
// e[i][j]=getchar();
cin>>e[i][j];
sum[i][j]=++ct;
// cout<<sum[i][j]<<endl;
// cout<<e[i][j];
}
// getchar();//换行
// puts("");
}
scanf("%d%d%d%d",&x_1,&y_1,&x_2,&y_2);
x_1++,y_1++,x_2++,y_2++;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int pos=(i-1)*m+j;
// cout<<pos<<endl;
// cout<<sum[i][j]<<endl;
if(j+1<=m)
{
add(pos,pos+1,(e[i][j]==e[i][j+1])?0:1);//右
// if(e[i][j]==e[i][j+1]) add(sum[i][j],sum[i][j+1],0);
// else add(sum[i][j],sum[i][j+1],1);
// add(sum[i][j],sum[i][j+1],(e[i][j]==e[i][j+1])?0:1);
}
if(j-1>=1)
{
add(pos,pos-1,(e[i][j]==e[i][j-1])?0:1);//左
// if(e[i][j]==e[i][j-1]) add(sum[i][j],sum[i][j-1],0);
// else add(sum[i][j],sum[i][j-1],1);
// add(sum[i][j],sum[i][j-1],(e[i][j]==e[i][j-1])?0:1);
}
if(i-1>=1)
{
add(pos,pos-m,(e[i][j]==e[i-1][j])?0:1);//上
// if(e[i][j]==e[i-1][j]) add(sum[i][j],sum[i-1][j],0);
// else add(sum[i][j],sum[i-1][j],1);
// add(sum[i][j],sum[i-1][j],(e[i][j]==e[i-1][j])?0:1);
}
if(i+1<=n)
{
add(pos,pos+m,(e[i][j]==e[i+1][j])?0:1);//下
// if(e[i][j]==e[i+1][j]) add(sum[i][j],sum[i+1][j],0);
// else add(sum[i][j],sum[i+1][j],1);
// add(sum[i][j],sum[i+1][j],(e[i][j]==e[i+1][j])?0:1);
}
}
// Dijkstra((x1-1)*m+y1);
// Dijkstra(sum[x_1][y_1]);
SPFA(sum[x_1][y_1]);
// cout<<sum[x1][y1]<<endl;
// cout<<sum[x2][y2]<<endl;
// cout<<(x1-1)*m+y1<<endl;
// cout<<(x2-1)*m+y2<<endl;
// for(int i=1;i<=n*m;i++)
// printf("%d\n",dist[i]);
// printf("%d\n",dist[(x2-1)*m+y2]);
printf("%d\n",dist[sum[x_2][y_2]]);
}
return 0;
}