Atcoder C - Routing

https://atcoder.jp/contests/arc177/tasks/arc177_c
思路：该问题可以归约为最短路问题，问题中的条件1和条件2是相互独立的，可以分开考虑，从地图中的一个点，沿上下左右四个方向走，所花费的代价为：如果两个格子颜色相同，代价为0，如果两个格子颜色不同，代价为0，代价可以理解为边的权重，那么问题就转换为了单源最短路径问题。
可以使用SPFA算法求解。

#include<bits/stdc++.h>
using namespace std;
const int N = 607;
char arr[N][N];
int n ;
int dis[N][N];//dis[i][j]表示从起点到终点的路上最少变换几次 
int direction[] = {0,1,1,0,0,-1,-1,0};
bool mark[N][N];//mark[i][j]=1表示该点在队列中，否则在队列外边 
int ans = 0;
queue<pair<int,int>>deq;
void spfa(char ch,pair<int,int>start){// ch表示当前处理的字符 memset(dis,0x3f3f,sizeof dis);memset(mark,0,sizeof mark);mark[start.first][start.second] = 1; dis[start.first][start.second] = 0;deq.push(start);while(deq.size()){auto u = deq.front();deq.pop();mark[u.first][u.second] = 0;int now = dis[u.first][u.second]; for(int i = 0;i<8;i+=2){int x = u.first + direction[i];int y = u.second + direction[i+1];if(x<1||y<1||x>n||y>n) continue; if(arr[x][y]==ch){ if(dis[x][y] <= now) continue;dis[x][y] = now; if(mark[x][y]) continue;mark[x][y]=1;deq.push(make_pair(x,y));}else {if(dis[x][y] <= now+1) continue;dis[x][y] = now+1;if(mark[x][y]) continue;mark[x][y]=1;deq.push(make_pair(x,y));}}}
}
int main(){	cin>>n;for(int i = 1;i<=n;i++){scanf("%s",arr[i]+1); }spfa('R',make_pair(1,1));ans+=dis[n][n];spfa('B',make_pair(1,n));ans+=dis[n][1];cout<<ans<<endl; return 0;
}