题目描述
有一个 $m \times m$ 的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1 个金币。
另外， 你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？
输入格式
第一行包含两个正整数 $ m, n$，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。
接下来的 $ n $ 行，每行三个正整数 $ x, y, c$， 分别表示坐标为 $(x,y)$ 的格子有颜色 $ c$。
其中 $ c=1$ 代表黄色，$ c=0$ 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为 $(1, 1)$，右下角的坐标为 $( m, m)$。
棋盘上其余的格子都是无色。保证棋盘的左上角，也就是 $(1, 1)$ 一定是有颜色的。
输出格式
一个整数，表示花费的金币的最小值，如果无法到达，输出 -1。
样例 #1
样例输入 #1
5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0
样例输出 #1
8
样例 #2
样例输入 #2
5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0
样例输出 #2
-1
提示
样例 1 说明
棋盘的颜色如下表格所示，其中空白的部分表示无色。
| $红$ | $红$ | |||
|---|---|---|---|---|
| $黄$ | ||||
| $黄$ | $红$ | |||
| $黄$ | ||||
| $红$ |
从 $(1,1)$ 开始，走到 $(1,2)$ 不花费金币。
从 $(1,2)$ 向下走到 $(2,2)$ 花费 $1$ 枚金币。
从 $(2,2)$ 施展魔法，将 $(2,3)$ 变为黄色，花费 $2$ 枚金币。
从 $(2,2)$ 走到 $(2,3)$ 不花费金币。
从 $(2,3)$ 走到 $(3,3)$ 不花费金币。
从 $(3,3)$ 走到 $(3,4)$ 花费 $1$ 枚金币。
从 $(3,4)$ 走到 $(4,4)$ 花费 $1$ 枚金币。
从 $(4,4)$ 施展魔法，将 $(4,5)$ 变为黄色，花费 $ 2$ 枚金币。
从 $(4,4)$ 走到 $(4,5)$ 不花费金币。
从 $(4,5)$ 走到 $(5,5)$ 花费 $1$ 枚金币。
共花费 $8 $ 枚金币。
样例 2 说明
棋盘的颜色如下表格所示，其中空白的部分表示无色。
| $红$ | $红$ | |||
|---|---|---|---|---|
| $黄$ | ||||
| $黄$ | ||||
| $ $ $ $ $ $ $ $ $ $ $ $ | ||||
| $红$ |
从 $( 1, 1)$ 走到 $( 1, 2)$，不花费金币。
从 $( 1, 2)$ 走到 $( 2, 2)$，花费 $ 1 $ 金币。
施展魔法将 $( 2, 3)$ 变为黄色，并从 $( 2, 2)$ 走到 $( 2, 3)$ 花费 $ 2$ 金币。
从 $( 2, 3)$ 走到 $( 3, 3)$ 不花费金币。
从 $( 3, 3)$ 只能施展魔法到达 $( 3, 2),( 2, 3),( 3, 4),( 4, 3)$。
而从以上四点均无法到达 $( 5, 5)$，故无法到达终点，输出$-1$。
数据规模与约定
对于 $30\%$ 的数据，$1 ≤ m ≤ 5, 1 ≤ n ≤ 10$。
对于 $60\%$ 的数据，$1 ≤ m ≤ 20, 1 ≤ n ≤ 200$。
对于 $100\%$ 的数据，$1 ≤ m ≤ 100, 1 ≤ n ≤ 1,000$。
算法1
DFS+记忆化剪枝
看到走棋盘这种东西第一时间就想到DFS和BFS这种东西，但是本人BFS奇差无比 so当然直接暴力DFS…那肯定会毫无例外地挂掉的so记忆化剪枝
C++ 代码
#include <bits/stdc++.h>
#define maxn 100005
#define maxm 2000005
#define inf 0x3f3f3f3f
#define re register
using namespace std;
const int Inf = 1e9;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };
const int N = 110;
int f[N][N];
int m, n;
int dist[N][N];
void dfs(int x, int y, int coin, bool canUseMagic, int nowColor, bool prevMagic);
//突发奇想 声明函数
int main(){
fill(f[0], f[0] + N * N, -1);
fill(dist[0], dist[0] + N * N, Inf);
int x, y, c;
cin >> m >> n;
for (int i = 0; i < n; ++i){
cin >> x >> y >> c;
f[x - 1][y - 1] = c;
}
dfs(0, 0, 0, true, f[0][0], true);
if (dist[m - 1][m - 1] == Inf)
dist[m - 1][m - 1] = -1;
cout << dist[m - 1][m - 1] << endl;
}
void dfs(int x, int y, int coin, bool canUseMagic, int nowColor, bool prevMagic){
if (coin >= dist[x][y])
return;
dist[x][y] = coin;
if (x == m - 1 && y == m - 1)
return;
if (!prevMagic)
canUseMagic = true;
for (int i = 0; i < 4; ++i){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < m && ny >= 0 && ny < m){
if (nowColor == f[nx][ny])
dfs(nx, ny, coin, canUseMagic, nowColor, canUseMagic);
else if (f[nx][ny] == -1 && canUseMagic)
dfs(nx, ny, coin + 2, false, nowColor, true);
else if (f[nx][ny] != -1)
dfs(nx, ny, coin + 1, canUseMagic, f[nx][ny], canUseMagic);
}
}
}
算法2
最短路(Dijkstra)
时间复杂度
$O(nlog 2 n)$
C++ 代码
#include<bits/stdc++.h>
#define maxn 100005
#define maxm 2000005
#define inf 0x3f3f3f3f
#define re register
using namespace std;
template <typename Tp>
void read(Tp &x){
char c=getchar();x=0;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;
}
struct Edge{
int f,t,w,nxt;
}edge[maxm];
int head[maxn],etot=1;
void add_edge(int f,int t,int w){
edge[++etot]=(Edge){f,t,w,head[f]};
head[f]=etot;
}
int tr[maxn<<2],dis1[maxn<<2],bt;
int n,m,S,T;
void build(){
for(bt=1;bt<=n+1;bt<<=1);
for(re int i=1;i<=n;i++)tr[i+bt]=i;
memset(dis1,0x3f,sizeof(dis1));
}
void modify(int x,int val){
dis1[x]=val;x+=bt;
for(x>>=1;x;x>>=1){
if(dis1[tr[x<<1]]<dis1[tr[(x<<1)|1]])tr[x]=tr[x<<1];
else tr[x]=tr[(x<<1)|1];
}
}
int dis[maxn];
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
build();
dis[S]=0;modify(S,0);
int x,y,w;
for(re int j=1;j<=n;j++){
x=tr[1];modify(x,inf);
for(re int i=head[x];i;i=edge[i].nxt){
y=edge[i].t;w=edge[i].w;
if(dis[y]>dis[x]+w){
dis[y]=dis[x]+w;
modify(y,dis[y]);
}
}
}
}
int dx[]={0,1,0,-1,1,1,-1,-1,0,2,0,-2};
int dy[]={1,0,-1,0,1,-1,1,-1,2,0,-2,0};
int dw[]={0,0,0,0,2,2,2,2,2,2,2,2};
int a[105][105],cnt[105][105];
struct node{
int x,y,c;
}b[maxn];
void preprocess(){
int x,y,c,xx,yy,ww;
for(re int i=1;i<=n;i++){
x=b[i].x;y=b[i].y;c=b[i].c;
for(re int j=0;j<12;j++){
xx=x+dx[j];yy=y+dy[j];ww=dw[j];
if(a[xx][yy]){
if(a[xx][yy]!=c)ww++;
add_edge(i,cnt[xx][yy],ww);
}
}
}
S=cnt[1][1];
}
int main(){
int mm,x,y,c;
read(mm);read(n);
for(re int i=1;i<=n;i++){
read(x);read(y);read(c);
a[x][y]=c+1;cnt[x][y]=i;
b[i]=(node){x,y,c+1};
}
preprocess();
dijkstra();
if(!a[mm][mm]){
int ans=min(dis[cnt[mm][mm-1]],dis[cnt[mm-1][mm]])+2;
if(ans>=inf)puts("-1");
else printf("%d\n",ans);
}
else{
if(dis[cnt[mm][mm]]==inf)puts("-1");
else printf("%d\n",dis[cnt[mm][mm]]);
}
return 0;
}
这个Dijkstra太基础了就不讲了吧
算法3
这是一个格子图，怎么把它转化成普通图呢
不难想到用格子做点，相邻格子同色边权为0，异色边权为1，无色不连边
但是，魔法怎么办？
考虑到魔法用完以后就会消失，相当于耗费2或3金币走两步。那么对于刚才没有连边的格子，将与无色格子相邻的有色格子与当前格子连边，同色边权为2，异色边权为3
接下来又有一个问题，如果终点无色，那么他就不会被连边，那么永远也无法到这个点，所以要预处理，把$m + 1$，然后把终点右边、下边的格子分别涂成红色、黄色，就OK了
时间复杂度
$O(n^2)$
C++ 代码
#include<bits/stdc++.h>
#define maxn 100005
#define maxm 2000005
#define inf 0x3f3f3f3f
#define re register
using namespace std;
const int INF=0x3fffffff;
const int MAX_M=109;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
int m;
int dis[MAX_M][MAX_M];
int chart[MAX_M][MAX_M];
struct edge_t{
int x,y,weight;
edge_t(int x_,int y_,int weight_):
x(x_),y(y_),weight(weight_){}
};
struct queue_element{
int x,y,dis_value;
queue_element(int x_,int y_,int dis_value_):
x(x_),y(y_),dis_value(dis_value_){}
bool operator < (const queue_element &other) const
{
return dis_value>other.dis_value;
}
};
vector<edge_t> edges[MAX_M][MAX_M];
bool xy_valid(int x,int y){
return 1<=x&&x<=m&&1<=y&&y<=m;
}
void add_edge(int x0,int y0,int x1,int y1,int weight){
edges[x0][y0].push_back(edge_t(x1,y1,weight));
}
void add_neighbors(int x,int y){
if(chart[x][y]==0)
return;
for(int i=0;i<4;++i){
int tx=x+dx[i],ty=y+dy[i];
if(!xy_valid(tx,ty))
continue;
if(chart[tx][ty]!=0){
add_edge(x,y,tx,ty,chart[x][y]==chart[tx][ty]?0:1);
continue;
}
for(int j=0;j<4;++j){
int ux=tx+dx[j],uy=ty+dy[j];
if(!xy_valid(ux,uy)||(ux==x&&uy==y)||chart[ux][uy]==0)
continue;
add_edge(x,y,ux,uy,chart[x][y]==chart[ux][uy]?2:3);
}
}
}
void dijkstra(){
priority_queue<queue_element> q;
q.push(queue_element(1,1,0));
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
dis[i][j]=INF;
while(!q.empty()){
queue_element t=q.top();
q.pop();
if(dis[t.x][t.y]!=INF)
continue;
dis[t.x][t.y]=t.dis_value;
for(vector<edge_t>::const_iterator e=edges[t.x][t.y].begin();e!=edges[t.x][t.y].end();++e)
q.push(queue_element(e->x,e->y,t.dis_value+e->weight));
}
}
int main(){
int n;
cin>>m>>n;
for(int i=0;i<n;++i){
int x,y,c;
cin>>x>>y>>c;
chart[x][y]=c+1;
}
++m;
chart[m-1][m]=1;
chart[m][m-1]=2;
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
add_neighbors(i,j);
dijkstra();
int ans=min(dis[m-1][m],dis[m][m-1]);
cout<<(ans==INF?-1:ans)<<'\n';
return 0;
}
