做网站设计答辩问题,辽宁手机版建站系统信息,网站制作合同范本,成都网站建设推进方案https://atcoder.jp/contests/arc177/tasks/arc177_c 思路#xff1a;该问题可以归约为最短路问题#xff0c;问题中的条件1和条件2是相互独立的#xff0c;可以分开考虑#xff0c;从地图中的一个点#xff0c;沿上下左右四个方向走#xff0c;所花费的代价为#xff1…https://atcoder.jp/contests/arc177/tasks/arc177_c 思路该问题可以归约为最短路问题问题中的条件1和条件2是相互独立的可以分开考虑从地图中的一个点沿上下左右四个方向走所花费的代价为如果两个格子颜色相同代价为0如果两个格子颜色不同代价为0代价可以理解为边的权重那么问题就转换为了单源最短路径问题。 可以使用SPFA算法求解。
#includebits/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;
queuepairint,intdeq;
void spfa(char ch,pairint,intstart){// 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;i8;i2){int x u.first direction[i];int y u.second direction[i1];if(x1||y1||xn||yn) 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] now1) continue;dis[x][y] now1;if(mark[x][y]) continue;mark[x][y]1;deq.push(make_pair(x,y));}}}
}
int main(){ cinn;for(int i 1;in;i){scanf(%s,arr[i]1); }spfa(R,make_pair(1,1));ansdis[n][n];spfa(B,make_pair(1,n));ansdis[n][1];coutansendl; return 0;
}
