POJ2688状态压缩（可以+DFS剪枝）
状态 可以 压缩 DFS 剪枝
2023-09-11 14:14:00 时间
题意：
给你一个n*m的格子，然后给你一个起点，让你遍历所有的垃圾，就是终点不唯一，问你最小路径是多少？
思路：
水题，方法比较多，最省事的就是直接就一个BFS状态压缩暴搜就行了，时间复杂度20*20*1024的，完全可以接受，但是被坑了，一开始怎么交都TLE，后来又写了一个BFS+DFS优化，就是跑之前先遍历一遍图，看看是不是所有的垃圾点都能遍历到，这样还是超时，无奈看了下讨论，有人说用G++交就行了，我用G++交了结果两个方法都AC了，哎！下面是两个方法的代码，比较简单，最近就是无聊，上POJ来刷刷水题，还有这个题目，可以用DP去做，还有就是可以直接求出任意两个垃圾的最短距离，然后在枚举处理垃圾顺序，枚举可以用STL的全排列，也可以搜索，这样的时间复杂度大约是N!吧，跟直接暴搜没啥区别，想试的可以敲敲试试吧。
直接BFS状态压缩暴力625
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef struct
{
int x ,y ,k ,t;
}NODE;
NODE xin ,tou;
int map[22][22] ,n ,m ,w;
int mark[22][22][1025];
int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};
bool ok(int x ,int y ,int k)
{
return x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] && !mark[x][y][k];
}
int BFS(int x ,int y)
{
queue<NODE>q;
xin.x = x ,xin.y = y;
xin.t = 0 ,xin.k = 0;
memset(mark ,0 ,sizeof(mark));
mark[xin.x][xin.y][xin.k] = 1;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int i = 0 ;i < 4 ;i ++)
{
xin.x = tou.x + dir[i][0];
xin.y = tou.y + dir[i][1];
xin.t = tou.t + 1;
if(map[xin.x][xin.y] && map[xin.x][xin.y] != -1)
xin.k = tou.k | (1 << (map[xin.x][xin.y] - 1));
else xin.k = tou.k;
if(ok(xin.x ,xin.y ,xin.k))
{
mark[xin.x][xin.y][xin.k] = 1;
q.push(xin);
if(xin.k == (1 << w) - 1) return xin.t;
}
}
}
return -1;
}
int main ()
{
char str[22];
int x ,y;
while(~scanf("%d %d" ,&m ,&n) && n+m)
{
w = 0;
for(int i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
for(int j = 1 ;j <= m ;j ++)
{
if(str[j-1] == '.') map[i][j] = -1;
else if(str[j-1] == '*') map[i][j] = ++w;
else if(str[j-1] == 'x') map[i][j] = 0;
else x = i ,y = j ,map[i][j] = -1;
}
}
w ? printf("%d\n" ,BFS(x ,y)):printf("0\n");
}
return 0;
}
BFS+DFS剪枝594
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef struct
{
int x ,y ,k ,t;
}NODE;
NODE xin ,tou;
int col[22][22] ,cmk[22][22];
int map[22][22] ,n ,m ,w;
int mark[22][22][1025];
int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};
bool ok(int x ,int y ,int k)
{
return x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] && !mark[x][y][k];
}
int BFS(int x ,int y)
{
queue<NODE>q;
xin.x = x ,xin.y = y;
xin.t = 0 ,xin.k = 0;
memset(mark ,0 ,sizeof(mark));
mark[xin.x][xin.y][xin.k] = 1;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int i = 0 ;i < 4 ;i ++)
{
xin.x = tou.x + dir[i][0];
xin.y = tou.y + dir[i][1];
xin.t = tou.t + 1;
if(map[xin.x][xin.y] && map[xin.x][xin.y] != -1)
xin.k = tou.k | (1 << (map[xin.x][xin.y] - 1));
else xin.k = tou.k;
if(ok(xin.x ,xin.y ,xin.k))
{
mark[xin.x][xin.y][xin.k] = 1;
q.push(xin);
if(xin.k == (1 << w) - 1) return xin.t;
}
}
}
return -1;
}
void DFS(int x ,int y)
{
for(int i = 0 ;i < 4 ;i ++)
{
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && !cmk[xx][yy] && map[xx][yy])
{
cmk[xx][yy] = 1;
DFS(xx ,yy);
}
}
}
int main ()
{
char str[22];
int x ,y;
while(~scanf("%d %d" ,&m ,&n) && n+m)
{
w = 0;
for(int i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
for(int j = 1 ;j <= m ;j ++)
{
if(str[j-1] == '.') map[i][j] = -1;
else if(str[j-1] == '*') map[i][j] = ++w;
else if(str[j-1] == 'x') map[i][j] = 0;
else x = i ,y = j ,map[i][j] = -1;
}
}
memset(cmk ,0 ,sizeof(cmk));
DFS(x ,y);
int mk = 0;
for(int i = 1 ;i <= n && !mk;i ++)
for(int j = 1 ;j <= m && !mk;j ++)
if(map[i][j] != -1 && map[i][j] && !cmk[i][j])
mk = 1;
if(mk)
{
printf("-1\n");
continue;
}
w ? printf("%d\n" ,BFS(x ,y)):printf("0\n");
}
return 0;
}
给你一个n*m的格子，然后给你一个起点，让你遍历所有的垃圾，就是终点不唯一，问你最小路径是多少？
思路：
水题，方法比较多，最省事的就是直接就一个BFS状态压缩暴搜就行了，时间复杂度20*20*1024的，完全可以接受，但是被坑了，一开始怎么交都TLE，后来又写了一个BFS+DFS优化，就是跑之前先遍历一遍图，看看是不是所有的垃圾点都能遍历到，这样还是超时，无奈看了下讨论，有人说用G++交就行了，我用G++交了结果两个方法都AC了，哎！下面是两个方法的代码，比较简单，最近就是无聊，上POJ来刷刷水题，还有这个题目，可以用DP去做，还有就是可以直接求出任意两个垃圾的最短距离，然后在枚举处理垃圾顺序，枚举可以用STL的全排列，也可以搜索，这样的时间复杂度大约是N!吧，跟直接暴搜没啥区别，想试的可以敲敲试试吧。
直接BFS状态压缩暴力625
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef struct
{
int x ,y ,k ,t;
}NODE;
NODE xin ,tou;
int map[22][22] ,n ,m ,w;
int mark[22][22][1025];
int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};
bool ok(int x ,int y ,int k)
{
return x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] && !mark[x][y][k];
}
int BFS(int x ,int y)
{
queue<NODE>q;
xin.x = x ,xin.y = y;
xin.t = 0 ,xin.k = 0;
memset(mark ,0 ,sizeof(mark));
mark[xin.x][xin.y][xin.k] = 1;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int i = 0 ;i < 4 ;i ++)
{
xin.x = tou.x + dir[i][0];
xin.y = tou.y + dir[i][1];
xin.t = tou.t + 1;
if(map[xin.x][xin.y] && map[xin.x][xin.y] != -1)
xin.k = tou.k | (1 << (map[xin.x][xin.y] - 1));
else xin.k = tou.k;
if(ok(xin.x ,xin.y ,xin.k))
{
mark[xin.x][xin.y][xin.k] = 1;
q.push(xin);
if(xin.k == (1 << w) - 1) return xin.t;
}
}
}
return -1;
}
int main ()
{
char str[22];
int x ,y;
while(~scanf("%d %d" ,&m ,&n) && n+m)
{
w = 0;
for(int i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
for(int j = 1 ;j <= m ;j ++)
{
if(str[j-1] == '.') map[i][j] = -1;
else if(str[j-1] == '*') map[i][j] = ++w;
else if(str[j-1] == 'x') map[i][j] = 0;
else x = i ,y = j ,map[i][j] = -1;
}
}
w ? printf("%d\n" ,BFS(x ,y)):printf("0\n");
}
return 0;
}
BFS+DFS剪枝594
#include<queue>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef struct
{
int x ,y ,k ,t;
}NODE;
NODE xin ,tou;
int col[22][22] ,cmk[22][22];
int map[22][22] ,n ,m ,w;
int mark[22][22][1025];
int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};
bool ok(int x ,int y ,int k)
{
return x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] && !mark[x][y][k];
}
int BFS(int x ,int y)
{
queue<NODE>q;
xin.x = x ,xin.y = y;
xin.t = 0 ,xin.k = 0;
memset(mark ,0 ,sizeof(mark));
mark[xin.x][xin.y][xin.k] = 1;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int i = 0 ;i < 4 ;i ++)
{
xin.x = tou.x + dir[i][0];
xin.y = tou.y + dir[i][1];
xin.t = tou.t + 1;
if(map[xin.x][xin.y] && map[xin.x][xin.y] != -1)
xin.k = tou.k | (1 << (map[xin.x][xin.y] - 1));
else xin.k = tou.k;
if(ok(xin.x ,xin.y ,xin.k))
{
mark[xin.x][xin.y][xin.k] = 1;
q.push(xin);
if(xin.k == (1 << w) - 1) return xin.t;
}
}
}
return -1;
}
void DFS(int x ,int y)
{
for(int i = 0 ;i < 4 ;i ++)
{
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && !cmk[xx][yy] && map[xx][yy])
{
cmk[xx][yy] = 1;
DFS(xx ,yy);
}
}
}
int main ()
{
char str[22];
int x ,y;
while(~scanf("%d %d" ,&m ,&n) && n+m)
{
w = 0;
for(int i = 1 ;i <= n ;i ++)
{
scanf("%s" ,str);
for(int j = 1 ;j <= m ;j ++)
{
if(str[j-1] == '.') map[i][j] = -1;
else if(str[j-1] == '*') map[i][j] = ++w;
else if(str[j-1] == 'x') map[i][j] = 0;
else x = i ,y = j ,map[i][j] = -1;
}
}
memset(cmk ,0 ,sizeof(cmk));
DFS(x ,y);
int mk = 0;
for(int i = 1 ;i <= n && !mk;i ++)
for(int j = 1 ;j <= m && !mk;j ++)
if(map[i][j] != -1 && map[i][j] && !cmk[i][j])
mk = 1;
if(mk)
{
printf("-1\n");
continue;
}
w ? printf("%d\n" ,BFS(x ,y)):printf("0\n");
}
return 0;
}
相关文章
- HA模式手动切换namenode状态
- Android实例-监测网络状态及一些事件(XE8+小米2)
- 常见HTTP状态码列表
- MS SQL 错误 ：17883，严重度: 1，状态: 0
- 调用链路上千条，如何观测 Nacos 的运行状态
- 【刷题】面筋-网络-HTTP的请求类型和状态码
- 查看 SELinux状态及关闭SELinux
- stat file 查看文件的 最新的被访问时间 最近的修改时间 最近的状态改变时间
- java核心知识点学习----并发和并行的区别,进程和线程的区别,如何创建线程和线程的四种状态,什么是线程计时器
- 【状态估计】观测信号（包括异常值）的状态估计方法（Matlab代码实现）
- “动态规划”这词太吓人，其实可以叫“状态缓存”
- input checkbox复选框点击获取当前选中状态jquery
- React学习笔记（四）—— 组件通信与状态管理、Hooks、Redux、Mobx
- ceph集群状态持续监控
- TCP三次握手和Time-Wait状态
- Pytest自动化框架之权威教程14-缓存:使用跨执行状态