Luogu1979 NOIP2013D2T3 华容道 搜索、最短路
2024-08-20 08:48:44
题意:给出一个$N \times M$的棋盘,棋盘上有一些块可以移动,有一些块无法移动。$Q$次询问,每一次询问给出三个块$a,b,c$,将$a$块变为空格,空格旁边可移动的块可以与空格交换位置。问每一次询问中最小的将$b$块移动到$c$块最开始位置上的移动次数。$N , M \leq 30 , Q \leq 500$
我觉得我在$NOIP$考场上绝对会直接打暴力qwq
我们能够发现空格必须要在需要移动的格子的四周,而且不移动需要移动的格子,才能发挥效果。所以当空格在需要移动的格子旁边的时候,只有两种情况:①将需要移动的格子与空格交换位置;②将空格移动到需要移动的格子的另一侧。所以我们预处理:$f_{i,j,k,l}$表示将空格从格子$i,j$的方向$k$移动到方向$l$且不移动$(i,j)$的最少步数,可以通过$bfs$实现,复杂度$O(16N^2M^2)$
接下来就是一个类似于最短路的问题了。然而最开始空格与需要移动的格子不相邻,所以我们在每一次询问的时候,再一次$bfs$计算现在空格的位置到达需要移动的格子四周且不移动需要移动的格子的最少移动次数,然后跑$SPFA$即可。因为图很小,卡不了$SPFA$。
#include<bits/stdc++.h> using namespace std; inline int read(){ ; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)){ a = (a << ) + (a << ) + (c ^ '); c = getchar(); } return a; } ][] = {,,,,-,,,-}; ][][][] , dis[][][] , t[][] , N , M , Q; ][] , inq[][][]; struct be{ int x , y , dir; }now; queue < pair < int , int > > q; queue < be > q1; inline int SPFA(int aX , int aY , int bX , int bY , int cX , int cY){ while(!q.empty()) q.pop(); if(!canbe[aX][aY] || !canbe[bX][bY]) return 0x3f3f3f3f; memset(t , 0x3f , sizeof(t)); t[aX][aY] = ; q.push(make_pair(aX , aY)); while(!q.empty()){ pair < int , int > r = q.front(); q.pop(); if(r.first == bX && r.second == bY) return t[bX][bY]; ; i < ; i++) ] != cX || r.second + dir[i][] != cY) ]][r.second + dir[i][]]) ]][r.second + dir[i][]] > t[r.first][r.second] + ){ t[r.first + dir[i][]][r.second + dir[i][]] = t[r.first][r.second] + ; q.push(make_pair(r.first + dir[i][] , r.second + dir[i][])); } } return 0x3f3f3f3f; } inline void bfs(int sX , int sY , int tX , int tY){ ; i < ; i++) if(dis[sX][sY][i] != 0x3f3f3f3f){ inq[sX][sY][i] = ; q1.push((be){sX , sY , i}); } while(!q1.empty()){ now = q1.front(); inq[now.x][now.y][now.dir] = ; q1.pop(); if(now.x == tX && now.y == tY) continue; ; i < ; i++) if(now.dir != i){ int N = dis[now.x][now.y][now.dir] + f[now.x][now.y][now.dir][i]; if(dis[now.x][now.y][i] > N){ dis[now.x][now.y][i] = N; if(!inq[now.x][now.y][i]){ inq[now.x][now.y][i] = ; q1.push((be){now.x , now.y , i}); } } } ]][now.y + dir[now.dir][]][ - now.dir] > dis[now.x][now.y][now.dir] + ){ dis[now.x + dir[now.dir][]][now.y + dir[now.dir][]][ - now.dir] = dis[now.x][now.y][now.dir] + ; ]][now.y + dir[now.dir][]][ - now.dir]){ inq[now.x + dir[now.dir][]][now.y + dir[now.dir][]][ - now.dir] = ; q1.push((be){now.x + dir[now.dir][] , now.y + dir[now.dir][] , - now.dir}); } } } } int main(){ N = read(); M = read(); Q = read(); ; i <= N ; i++) ; j <= M ; j++) canbe[i][j] = read(); memset(f , 0x3f , sizeof(f)); ; i <= N ; i++) ; j <= M ; j++) if(canbe[i][j]) ; m <= ; m++) ; n <= ; n++) f[i][j][m][n] = SPFA(i + dir[m][] , j + dir[m][] , i + dir[n][] , j + dir[n][] , i , j); while(Q--){ int a = read() , b = read() , c = read() , d = read() , e = read() , f = read(); if(c == e && d == f){ printf("0\n"); continue; } memset(dis , 0x3f , sizeof(dis)); ; i < ; i++) dis[c][d][i] = SPFA(a , b , c + dir[i][] , d + dir[i][] , c , d); bfs(c , d , e , f); int ans = 0x3f3f3f3f; ; i < ; i++) ans = min(ans , dis[e][f][i]); printf( : ans); } ; }
最新文章
- 玩玩cordova(MAC安装环境)
- Android开发学习总结(六)—— APK反编译
- codeigniter 对数据库的常用操作
- 转:内存区划分、内存分配、常量存储区、堆、栈、自由存储区、全局区[C++][内存管理][转载]
- WS之cxf与spring整合1
- MySQL 多实例删库脚本
- 流媒體】jrtplib—VS2010下RTP开源协议库JRTPLIB3.9.1编译
- 1002 GTY&#39;s birthday gift
- 【行为型】Strategy模式
- sql server 2008 R2 压缩备份数据库
- PAT (Advanced Level) 1047. Student List for Course (25)
- rhel7 启动网络
- js_base_note
- python实现单例模式的三种方式及相关知识解释
- 剑指offer(15)
- 20190315xlVBA_删除无用的区域
- Quartz.net 定时任务之储存与持久化和集群(源码)
- 解决node使用中8080端口被占用
- [na]tcpdump非常实用的抓包实例
- autofac初识