题解 | #[NOIP2017]棋盘#
[NOIP2017]棋盘
https://ac.nowcoder.com/acm/problem/16423
#include<stdio.h>
#include<limits.h>
struct grid {
int x,y;
int color,magic;
int min_cost;
} grid[100][100];
int dx[4]= {0,0,1,-1},dy[4]= {1,-1,0,0};
struct grid queue[10000];//存疑
void bfs(int gridSize) {
int front=0,rear=0;
queue[rear++]=grid[0][0];
while(front!=rear) {
struct grid current=queue[front++];
//遍历四个方向
for(int i=0; i<4; i++) {
int NextX=current.x+dx[i],NextY=current.y+dy[i];
if(NextX>=gridSize||NextY>=gridSize||NextX<0||NextY<0) continue;
//相同
if(current.color==grid[NextX][NextY].color&¤t.min_cost<grid[NextX][NextY].min_cost) {
grid[NextX][NextY].min_cost=current.min_cost;
queue[rear++]=grid[NextX][NextY];
}
//不同
else if(current.color!=grid[NextX][NextY].color) {
//后一个节点颜色为0
if(!current.magic&&grid[NextX][NextY].color==0&¤t.min_cost+2<grid[NextX][NextY].min_cost){
grid[NextX][NextY].min_cost=current.min_cost+2;
queue[rear++]=(struct grid){NextX,NextY,current.color,1,current.min_cost+2};
}
//后一个节点颜色不为0
else if(grid[NextX][NextY].color!=0&¤t.min_cost+1<grid[NextX][NextY].min_cost) {
grid[NextX][NextY].min_cost=current.min_cost+1;
queue[rear++]=grid[NextX][NextY];
}
}
}
}
}
int main() {
int gridSize,colorSize;
scanf("%d%d",&gridSize,&colorSize);
for(int i=0; i<gridSize; i++)
for(int j=0; j<gridSize; j++)
grid[i][j]=(struct grid) {i,j,0,0,INT_MAX};
grid[0][0].min_cost=0;
for(int i=0; i<colorSize; i++) {
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
grid[x-1][y-1].color=c+1;
}
bfs(gridSize);
if(grid[gridSize-1][gridSize-1].min_cost==INT_MAX)
printf("-1\n");
else printf("%d\n",grid[gridSize-1][gridSize-1].min_cost);
}
