题目描述
小明最近喜欢玩一个游戏。给定一个n×m的棋盘，上面有两种格子
#和@。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是0，否则费用是1。请编程计算从起始位置移动到目标位置的最小花费。输入格式
输入文件有多组数据。
输入第一行包含两个整数n，m，分别表示棋盘的行数和列数。
输入接下来的n行，每一行有m个格子（使用#或者@表示）。
输入接下来一行有四个整数x1,y1,x2,y2，分别为起始位置和目标位置。
当输入n，m均为0时，表示输入结束。输出格式
对于每组数据，输出从起始位置到目标位置的最小花费。每一组数据独占一行。
输入输出样例
输入 #1复制
2 2 @# #@ 0 0 1 1 2 2 @@ @# 0 1 1 0 0 0输出 #1复制
2 0说明/提示
对于20%的数据满足：1≤n,m≤10。
对于40%的数据满足：1≤n,m≤300。
对于100%的数据满足：1≤n,m≤500。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long//宏定义
#define PII pair<int,int>
#define fi first
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};//向四个方向移动
int n,m,sx,sy,ex,ey;
//注意输入的起始和终止坐标都是从0开始的，计算和输出是横纵坐标各要加一
char sn[510][510];//存棋盘
int dis[510][510];//存到达某点的花费
bool vis[510][510];//存某点是否搜过
void distra(){//模板 改动
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
dis[i][j]=1e18;
vis[i][j]=0;//!!!掉的第一个坑 忘记初始化为0 只能完成第一组数据
}
}
priority_queue<pair<int,PII>,vector<pair<int,PII>>,greater<pair<int,PII>> > q;
//从小到大排序
q.push({0,{sx+1,sy+1}});//!!!掉的第二个坑，没注意给的数据横纵坐标从0开始
dis[sx+1][sy+1]=0;//起点的花费为0
while(q.size()){
auto t=q.top();//取对头，注意为q.top()而不是q.front()
q.pop();//出队
auto now=t.second;//取当前点坐标
if(vis[now.fi][now.second]==1) continue;//如果这个点搜过了就不搜
vis[now.fi][now.second]=1;
for(int i = 0;i<=3;i++){//向四个方向移动
int a=now.fi+dx[i],b=now.second+dy[i];
if(a>=1&&a<=n&&b>=1&&b<=m){//判断是否越界
if(sn[a][b]==sn[now.fi][now.second]&&dis[a][b]>dis[now.fi][now.second]){
//判断两个格子是否一样并且得到较小值
dis[a][b]=dis[now.fi][now.second];
q.push({dis[a][b],{a,b}});//入队
}else if(sn[a][b]!=sn[now.fi][now.second]&&dis[a][b]>dis[now.fi][now.second]+1){
dis[a][b]=dis[now.fi][now.second]+1;
q.push({dis[a][b],{a,b}});
}
}
}
}
}
signed main(){
while(1){//多组数据
cin >> n >> m;
if(n==0&&m==0) break;//结束循环的判断
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin >> sn[i][j];//输入棋盘
}
}
cin >> sx>>sy>>ex>>ey;
distra();
cout << dis[ex+1][ey+1]<<"\n";//!!!注意横纵坐标加一
}
return 0;
}