本文共 2103 字，大约阅读时间需要 7 分钟。
传送门：
题意：“#”是草，"."是墙，询问能不能点燃俩地方，即点燃俩“#”，把所有的草烧完，如果可以，那么输出最小需要的时间，如果不行输出-1
思路：暴力BFS，看到n和m都不大，直接把每个“#”都存下来，每次加入2个点进广搜搜能否烧完，然后更新ans即可。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long #define pb push_back #define mk make_pair #define pill pair #define mst(a, b) memset(a, b, sizeof a) #define REP(i, x, n) for(int i = x; i <= n; ++i)void closeio(){ cin.tie(0); ios::sync_with_stdio(0);}struct note{ int x,y,step;}p,pos;char ma[20][20];int vis[20][20];int n,m;int go[4][2] = { { 1,0},{-1,0},{ 0,-1},{ 0,1}};//四个方向void init(){ memset(vis,0,sizeof(vis));}bool check(int x,int y){ if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] == 1){ return false; } return true;}//判断是否越界和已经访问过bool judge(){ for(int i = 0 ; i < n ; i ++){ for(int j = 0 ; j < m ; j ++){ if(ma[i][j] == '#' && !vis[i][j]){ return false; } } } return true;}//判断是否满足全都着火了 int bfs(int x,int y,int a,int b){ int sum = 0; queue q; q.push((note){x,y,0}); vis[x][y] = 1; q.push((note){a,b,0}); vis[a][b] = 1; //把两个点都加入队列 while(!q.empty()){ pos = q.front(); sum = pos.step;//队列中最后一个点的step就是需要的步数 q.pop(); for(int i = 0 ; i < 4 ;i ++){ int dx = pos.x + go[i][0]; int dy = pos.y + go[i][1]; if(check(dx,dy) && ma[dx][dy] == '#'){ p.x = dx; p.y = dy; p.step = pos.step + 1; q.push(p); vis[dx][dy] = 1; } } } return sum;}int main(){ int t,cas = 1; for(scanf("%d",&t);t--;){ vector v; scanf("%d %d",&n,&m); for(int i = 0 ; i < n ; i++){ scanf("%s",ma[i]); for(int j = 0 ; j < m ; j ++){ if(ma[i][j] == '#'){ p.x = i;p.y = j;p.step = 0; v.push_back(p); } } } int ans = 10000000; for(int i = 0 ; i < v.size() ; i++){ for(int j = i ; j < v.size() ; j ++){ init(); int a = bfs(v[i].x,v[i].y,v[j].x,v[j].y); if(judge()){ ans = min(a,ans); }//如果都着火了，那么ans值取ans和这次广搜中小的那个 } } printf("Case %d: %d\n",cas++,ans == 10000000?-1:ans); } return 0;}
转载于:https://www.cnblogs.com/Esquecer/p/9013462.html