棋盘

链接：https://ac.nowcoder.com/acm/problem/16423
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 100;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int a[MAXN+5][MAXN+5];
int MIN[MAXN+5][MAXN+5][2];
struct NODE{
int x,y,t,c;
}p;
bool operator<(NODE a,NODE b)
{
return a.t>b.t;
}
priority_queue<node>que;
int main()
{
memset(a,-1,sizeof(a));
memset(MIN,63,sizeof(MIN));
int m,n;
scanf("%d %d",&m,&n);
for(int i=1;i<=n;i++)
{
int x,y,c;
scanf("%d %d %d",&x,&y,&c);
a[x][y] = c;
}
p.x = 1;p.y = 1;
p.t = 0;p.c = a[1][1];
MIN[1][1][a[1][1]] = 0;
que.push(p);
do
{
p = que.top();que.pop();
if( p.x == m && p.y == m )
{
printf("%d\n",p.t);
return 0;
}
if( p.t < MIN[p.x][p.y][p.c] ) continue;
for(int i=0;i<4;i++)
{
NODE q;
q.x = p.x + dir[i][0];
q.y = p.y + dir[i][1];
if( q.x < 1 || q.y < 1 || q.x > m || q.y > m ) continue;
if( a[q.x][q.y] == -1 )
{
if( a[p.x][p.y] == -1 ) continue;
q.t = p.t + 2;
q.c = p.c;
if( q.t < MIN[q.x][q.y][q.c] )
{
MIN[q.x][q.y][q.c] = q.t;
que.push(q);
}
q.c = !(p.c);
q.t++;
if( q.t < MIN[q.x][q.y][q.c] )
{
MIN[q.x][q.y][q.c] = q.t;
que.push(q);
}
}
else
{
q.t = p.t;q.c = a[q.x][q.y];
if( q.c != p.c ) q.t++;
if( q.t < MIN[q.x][q.y][q.c] )
{
MIN[q.x][q.y][q.c] = q.t;
que.push(q);
}
}
}
}while(!que.empty());
printf("-1\n");
return 0;
}</node></queue></cstring></cstdio>