没过的都是答案差1,看了2小时看不出来
by yycQAQ @ 2023-11-08 17:30:05
已过。
修改后代码
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100;
int n,m,a[101][101];
struct node{
int x,y,c,cha;
};
int vis[101][101];
int cost[101][101];
int x2[4]={-1,1,0,0};
int y2[4]={0,0,-1,1};
int que[101][101];
void bfs(){
queue<node> q;
node start={1,1,a[1][1],0};
cost[1][1]=0;
vis[1][1]=1;
q.push(start);
while(!q.empty()){
node u=q.front();
q.pop();
u.c=que[u.x][u.y];
//cout<<u.x<<" "<<u.y<<endl;
//vis[u.x][u.y]=1;
for(int i=0;i<4;i++){
int vx=u.x+x2[i],vy=u.y+y2[i];
if(vx<1||vx>n||vy<1||vy>n) continue;
if(!(a[vx][vy]==-1&&u.cha)){
//cout<<vx<<" "<<vy<<endl;
if(a[vx][vy]!=u.c&&a[vx][vy]!=-1){
//cout<<vx<<" "<<vy<<endl;
cost[vx][vy]=min(cost[u.x][u.y]+1,cost[vx][vy]);
if(!vis[vx][vy]){
q.push(node{vx,vy,que[vx][vy],0});
vis[vx][vy]=1;
}
}
else if(a[vx][vy]==u.c){
cost[vx][vy]=min(cost[u.x][u.y],cost[vx][vy]);
//cout<<vx<<" "<<vy<<endl;
if(!vis[vx][vy]){
q.push(node{vx,vy,que[vx][vy],0});
vis[vx][vy]=1;
}
}
else if(a[vx][vy]==-1){
// cout<<vx<<" "<<vy<<endl;
if(cost[vx][vy]>cost[u.x][u.y]+2){
cost[vx][vy]=cost[u.x][u.y]+2;
que[vx][vy]=a[u.x][u.y];
}
if(!vis[vx][vy]){
q.push(node{vx,vy,que[u.x][u.y],1});
vis[vx][vy]=1;
}
}
}
}
//vis[u.x][u.y]=0;
//cout<<endl;
}
}
signed main(){
memset(a,-1,sizeof(a));
memset(cost,0x3f3f3f3f,sizeof(cost));
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,c;
cin>>x>>y>>c;
a[x][y]=c;
que[x][y]=c;
}
bfs();
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// printf("%3d ",a[i][j]);
// }
// cout<<endl;
// }
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// if(cost[i][j]<100)printf("%3d ",cost[i][j]);
// else printf("INF ");
// }
// cout<<endl;
// }
if(vis[n][n]) cout<<cost[n][n];
else cout<<-1;
}
```
by yycQAQ @ 2023-11-08 18:08:57