FZU 2150 Fire Game
Description
今有草地一片，’#’为草，’.’为空地，草可燃，地不可。有二童子顽劣之至，以焚尽草地为娱。二人可于两处分别点火，瞬间即燃。火势凶猛，所到之处，寸草不生。凡火所在，唯待一刻，便四处蔓延。问：待草烧尽，耗时几何？
思路
各种点火组合皆遍历一遍,找出最优解。
BFS：将两个起点一起放入队列中遍历，vis数组标记该点是否已燃。检查终点，若所有草地被燃，答案即为终点时的time（我曾想问：若终点之前的某点以满足条件（即所有草地皆已燃），那答案是不是会更小些？后来想想这个点就是终点，vis尽被标记找不到其他点了）
吐槽
我也太那啥那啥了…一点不那啥…还是太那啥了…刚开始想着两个点”分别“但“同时“bfs，还担心一个vis不够用（这个火燃到这里应该允许另一个火也可以经过这），后来想想，都是火，分啥你我啊!
Code
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
string s[15];
bool flag;
bool vis[15][15];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int tot;
struct grass
{
int x, y;
} g[105];
struct node
{
int x, y, tim;
};
bool check()
{
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
if(!vis[i][j] && s[i][j] == '#')///有草地剩余
return 0;
}
return 1;
}
int bfs(grass a, grass b)
{
queue<node> q;
node first, nxt;
first.x = a.x;
first.y = a.y;
first.tim = 0;
vis[a.x][a.y] = 1;
q.push(first);
first.x = b.x;
first.y = b.y;
first.tim = 0;
vis[b.x][b.y] = 1;
q.push(first);
while(q.size())
{
first = q.front();
q.pop();
for(int i = 0; i < 4; ++i)
{
int xx = first.x + dx[i];
int yy = first.y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && s[xx][yy] == '#' )
{
vis[xx][yy] = 1;
nxt.x = xx;
nxt.y = yy;
nxt.tim = first.tim + 1;
q.push(nxt);
}
}
}
if(check())
return first.tim;
return inf;
}
int main()
{
// freopen("00in.txt", "r", stdin);
int t;
cin >> t;
int tem = t;
while(t--)
{
tot = 0;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
cin >> s[i];
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(s[i][j] == '#')
{
g[tot].x = i;
g[tot].y = j;
tot++;
}
flag = 0;
int ans = inf;
for(int i = 0; i < tot; ++i)
for(int j = i; j < tot; ++j)///j == i不能漏（只有一处可点的地方）
{
memset(vis, 0, sizeof(vis));
int res = bfs(g[i], g[j]);
if(res < ans)
ans = res;
}
if(ans == inf)
cout << "Case " << tem - t << ": -1" << '\n';
else
cout << "Case " << tem - t << ": " << ans << '\n';
}
return 0;
}
Just say something I want to say
刚开始做这题有自己的想法，然后发现漏洞，各种弥补，一点一点添置，一点一点改进，结果写了二百多行，写了三天还是…写的
江郎才尽没办法了看了一眼题解，原来想多了，一些地方没想明白整的很复杂…这让我想起高中的时候，那时候要想得高分倡导多做题，不要吊死在一棵树上。可我做不到，这道题我有想法，付出再多精力与时间把它做出来也是值得的。可事实是即使这样我也做不出来，然而负反馈调节就出现了：我都付出那么多了必须把它做出来，可我就是做不出来，如果此时放弃那么岂不前功尽弃，如果此时不放弃岂不浪费更多时间…
这好像是心理学的某个定理（也可能不是）：你买了一张电影票，看了一会儿发现电影不怎么样，甚至有些厌恶，这时候明明可以离开的，可转念一想：钱都花了，不看完好像损失了什么。然而最终事实是：你浪费了时间去做了自己讨厌的事，一切似乎只是因为“患得患失”的性格？以说：当断则断？（能屈能伸？张弛有度？）说起来倒容易……
贴一些废代码泄愤（勿看）
#include <set>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
bool flag;///BFS can't find the answer,output "-1".
string s[15];
bool vis1[15][15];
bool vis2[15][15];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int zc[4];
int zd[4];///从某点出发可以走四个方向，起初自作聪明写3
int tot;
struct grass
{
int x, y;
} g[105];
struct node
{
int x, y, tim;
set<int> st;///存放当前状态已燃之草的序号
} ;
int bfs(grass c, grass d)
{
bool flag1 = 0;
bool flag2 = 0;
node nowc, nowd, nxtc[4], nxtd[4], last1, last2;
nowc.x = c.x;
nowc.y = c.y;
nowc.tim = 0;
for(int i = 0; i < tot; ++i)
if(g[i].x == c.x && g[i].y == c.y)
{
nowc.st.insert(i);
break;
}
vis1[c.x][c.y] = 1;
queue<node> q1;
q1.push(nowc);
nowd.x = d.x;
nowd.y = d.y;
nowd.tim = 0;
for(int i = 0; i < tot; ++i)
if(g[i].x == d.x && g[i].y == d.y)
{
nowd.st.insert(i);
break;
}
vis2[d.x][d.y] = 1;
queue<node> q2;
q2.push(nowd);
while(q1.size() || q2.size())
{
///取队列首元素
if(q1.size() == 1)
last1 = q1.front();
if(q2.size() == 1)
last2 = q2.front();
if(q1.empty())
nowc = last1;
else
{
flag1 = 1;
nowc = q1.front();
q1.pop();
}
if(q2.empty())
nowd = last2;
else
{
flag2 = 1;
nowd = q2.front();
q2.pop();
}
cout << "have a check : " << '\n';
cout << "nowc " << nowc.x << ' ' << nowc.y << ' ' << nowc.tim << ' ' << nowc.st.size() << '\n';
cout << "nowd " << nowd.x << ' ' << nowd.y << ' ' << nowd.tim << ' ' << nowd.st.size() << '\n';
///出口判断
if(nowc.st.size() + nowd.st.size() >= tot)
{
cout << "It seems to be a exit." << '\n';
set<int> totst = nowc.st;
for(set<int> ::iterator it = nowd.st.begin(); it != nowd.st.end(); ++it)
totst.insert(*it);
cout << "tot : " << totst.size() << '\n';
if(totst.size() == tot)
{
flag = 1;
cout << "The ans is : " << nowc.tim + nowd.tim << '\n';
return nowc.tim + nowd.tim;
}
// flag = 1;
// if(nowc.st.size() == tot && nowd.st.size() != tot)
// {
// cout << "The ans is : " << nowc.tim << '\n';
// return nowc.tim;
// }
// else if(nowd.st.size() == tot && nowc.st.size() != tot)
// {
// cout << "The ans is : " << nowd.tim << '\n';
// return nowd.tim;
// }
// else
// {
// cout << "The ans is : " << min(nowc.tim, nowd.tim) << '\n';
// return min(nowc.tim, nowd.tim);
// }
}
///搜索nxt
int zcnum = 0;
int zdnum = 0;
memset(zc, 0, sizeof(zc));
memset(zd, 0, sizeof(zd));
int nxtcnum = 0;
int nxtdnum = 0;
for(int i = 0; i < 4; ++i)
{
int xx, yy;
if(flag1)
{
xx = nowc.x + dx[i];
yy = nowc.y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis1[xx][yy] && s[xx][yy] == '#')
{
vis1[xx][yy] = 1;
nxtc[nxtcnum].x = xx;
nxtc[nxtcnum].y = yy;
nxtcnum++;
// nxtc.tim = nowc.tim + 1;
// nxtc.st = nowc.st;
for(int j = 0; j < tot; ++j)
if(g[j].x == xx && g[j].y == yy)
{
zc[zcnum++] = j;
break;
}
// q1.push(nxtc);
}
}
if(flag2)
{
xx = nowd.x + dx[i];
yy = nowd.y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis2[xx][yy] && s[xx][yy] == '#')
{
vis2[xx][yy] = 1;
nxtd[nxtdnum].x = xx;
nxtd[nxtdnum].y = yy;
nxtdnum++;
// nxtd.tim = nowd.tim + 1;
// nxtd.st = nowd.st;
for(int j = 0; j < tot; ++j)
if(g[j].x == xx && g[j].y == yy)
{
zd[zdnum++] = j;
break;
}
// q2.push(nxtd);
}
}
}
for(int i = 0; i < nxtcnum; ++i)
{
nxtc[i].tim = nowc.tim + 1;
nxtc[i].st = nowc.st;
for(int j = 0; j < zcnum; ++j)
nxtc[i].st.insert(zc[j]);
q1.push(nxtc[i]);
}
for(int i = 0; i < nxtdnum; ++i)
{
nxtd[i].tim = nowd.tim + 1;
nxtd[i].st = nowd.st;
for(int j = 0; j < zdnum; ++j)
nxtd[i].st.insert(zd[j]);
q2.push(nxtd[i]);
}
}
cout << "There is no solution!" << '\n';
return inf;
}
int main()
{
int t;
freopen("00in.txt", "r", stdin);
cin >> t;
int tem = t;
while(t--)
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
cin >> s[i];
tot = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(s[i][j] == '#')
{
g[tot].x = i;
g[tot].y = j;
tot++;
}
if(tot <= 2)
{
if(tot > 0)
{
cout << "the number of the grass is less than 3" << '\n';
cout << "Case :" << tem - t << ": 0" << '\n';
}
else
{
cout << "there is no grass!" << '\n';
cout << "Case :" << tem - t << ": -1" << '\n';
}
}
else
{
int ans = inf;
flag = 0;///0表示无合适方案
for(int i = 0; i < tot; ++i)
for(int j = i + 1; j < tot; ++j)
{
cout << "The new solution for this question :" << '\n';
cout << "position :" << g[i].x << ' ' << g[i].y << ' ' << g[j].x << ' ' << g[j].y << '\n';
memset(vis1, 0, sizeof(vis1));
memset(vis2, 0, sizeof(vis2));
int res = bfs(g[i], g[j]);
if(res < ans)
ans = res;
}
if(flag)
cout << "Case :" << tem - t << ": " << ans << '\n';
else
cout << "Case :" << tem - t << ": -1" << '\n';
}
}
return 0;
}
#include <set>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
bool flag;///BFS can't find the answer,output "-1".
string s[15];
bool vis1[15][15];
bool vis2[15][15];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int zc[4];
int zd[4];///从某点出发可以走四个方向，起初自作聪明写3
int tot;
struct grass
{
int x, y;
} g[105];
struct node
{
int x, y, tim;
set<int> st;///存放当前状态已燃之草的序号
} ;
int bfs(grass c, grass d)
{
bool flag1 = 0;
bool flag2 = 0;
node nowc, nowd, nxtc, nxtd, last1, last2;
nowc.x = c.x;
nowc.y = c.y;
nowc.tim = 0;
for(int i = 0; i < tot; ++i)
if(g[i].x == c.x && g[i].y == c.y)
{
nowc.st.insert(i);
break;
}
vis1[c.x][c.y] = 1;
queue<node> q1;
q1.push(nowc);
nowd.x = d.x;
nowd.y = d.y;
nowd.tim = 0;
for(int i = 0; i < tot; ++i)
if(g[i].x == d.x && g[i].y == d.y)
{
nowd.st.insert(i);
break;
}
vis2[d.x][d.y] = 1;
queue<node> q2;
q2.push(nowd);
while(q1.size() || q2.size())
{
///取队列首元素
if(q1.size() == 1)
last1 = q1.front();
if(q2.size() == 1)
last2 = q2.front();
if(q1.empty())
nowc = last1;
else
{
flag1 = 1;
nowc = q1.front();
q1.pop();
}
if(q2.empty())
nowd = last2;
else
{
flag2 = 1;
nowd = q2.front();
q2.pop();
}
cout << "have a check : " << '\n';
cout << "nowc " << nowc.x << ' ' << nowc.y << ' ' << nowc.tim << ' ' << nowc.st.size() << '\n';
cout << "nowd " << nowd.x << ' ' << nowd.y << ' ' << nowd.tim << ' ' << nowd.st.size() << '\n';
///出口判断
// if(nowc.st.size() + nowd.st.size() >= tot)
// {
// cout << "It seems to be a exit." << '\n';
// set<int> totst = nowc.st;
// for(set<int> ::iterator it = nowd.st.begin(); it != nowd.st.end(); ++it)
// totst.insert(*it);
// cout << "tot : " << totst.size() << '\n';
// if(totst.size() == tot)
// {
// flag = 1;
// cout << "The ans is : " << nowc.tim + nowd.tim << '\n';
// return nowc.tim + nowd.tim;
// }
// flag = 1;
// if(nowc.st.size() == tot && nowd.st.size() != tot)
// {
// cout << "The ans is : " << nowc.tim << '\n';
// return nowc.tim;
// }
// else if(nowd.st.size() == tot && nowc.st.size() != tot)
// {
// cout << "The ans is : " << nowd.tim << '\n';
// return nowd.tim;
// }
// else
// {
// cout << "The ans is : " << min(nowc.tim, nowd.tim) << '\n';
// return min(nowc.tim, nowd.tim);
// }
// }
///搜索nxt
// int zcnum = 0;
// int zdnum = 0;
// memset(zc, 0, sizeof(zc));
// memset(zd, 0, sizeof(zd));
// int nxtcnum = 0;
// int nxtdnum = 0;
for(int i = 0; i < 4; ++i)
{
int xx, yy;
if(flag1)
{
xx = nowc.x + dx[i];
yy = nowc.y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis1[xx][yy] && s[xx][yy] == '#')
{
vis1[xx][yy] = 1;
nxtc.x = xx;
nxtc.y = yy;
nxtc.tim = nowc.tim + 1;
nxtc.st = nowc.st;
for(int j = 0; j < tot; ++j)
if(g[j].x == xx && g[j].y == yy)
{
nxtc.st.insert(j);
break;
}
q1.push(nxtc);
}
}
if(flag2)
{
xx = nowd.x + dx[i];
yy = nowd.y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis2[xx][yy] && s[xx][yy] == '#')
{
vis2[xx][yy] = 1;
nxtd.x = xx;
nxtd.y = yy;
nxtd.tim = nowd.tim + 1;
nxtd.st = nowd.st;
for(int j = 0; j < tot; ++j)
if(g[j].x == xx && g[j].y == yy)
{
nxtd.st.insert(j);
break;
}
q2.push(nxtd);
}
}
}
// for(int i = 0; i < nxtcnum; ++i)
// {
// nxtc[i].tim = nowc.tim + 1;
// nxtc[i].st = nowc.st;
// for(int j = 0; j < zcnum; ++j)
// nxtc[i].st.insert(zc[j]);
// q1.push(nxtc[i]);
// }
// for(int i = 0; i < nxtdnum; ++i)
// {
// nxtd[i].tim = nowd.tim + 1;
// nxtd[i].st = nowd.st;
// for(int j = 0; j < zdnum; ++j)
// nxtd[i].st.insert(zd[j]);
// q2.push(nxtd[i]);
// }
}
cout << "There is no solution!" << '\n';
return inf;
}
int main()
{
int t;
freopen("00in.txt", "r", stdin);
cin >> t;
int tem = t;
while(t--)
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
cin >> s[i];
tot = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(s[i][j] == '#')
{
g[tot].x = i;
g[tot].y = j;
tot++;
}
if(tot <= 2)
{
if(tot > 0)
{
cout << "the number of the grass is less than 3" << '\n';
cout << "Case :" << tem - t << ": 0" << '\n';
}
else
{
cout << "there is no grass!" << '\n';
cout << "Case :" << tem - t << ": -1" << '\n';
}
}
else
{
int ans = inf;
flag = 0;///0表示无合适方案
for(int i = 0; i < tot; ++i)
for(int j = i + 1; j < tot; ++j)
{
cout << "The new solution for this question :" << '\n';
cout << "position :" << g[i].x << ' ' << g[i].y << ' ' << g[j].x << ' ' << g[j].y << '\n';
memset(vis1, 0, sizeof(vis1));
memset(vis2, 0, sizeof(vis2));
int res = bfs(g[i], g[j]);
if(res < ans)
ans = res;
}
if(flag)
cout << "Case :" << tem - t << ": " << ans << '\n';
else
cout << "Case :" << tem - t << ": -1" << '\n';
}
}
return 0;
}
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, ans;
bool flag;///针对 “-1”
string s[15];
bool vis1[15][15];
bool vis2[15][15];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct node
{
int x, y, step;
} a[100];
int tot;
struct grass
{
int x, y;
} g[100];
int bfs(grass c, grass d)
{
int num = 2;
node now1, now2, nxt1, nxt2;
int ans_step = 0;
now1.x = c.x;
now1.y = c.y;
now1.step = 0;
vis1[c.x][c.y] = 1;
now2.x = d.x;
now2.y = d.y;
now2.step = 0;
vis2[d.x][d.y] = 1;
queue<node> q1;
queue<node> q2;
q1.push(now1);
q2.push(now2);
while(q1.size() || q2.size())///刚开始记错了写成&&
{
// cout << "Check the size : " << '\n';
// cout << q1.size() << ' ' << q2.size() << '\n';
bool flag1 = 0;
bool flag2 = 0;
bool flag_front = 0;
if(q1.size())
{
flag1 = 1;
now1 = q1.front();
q1.pop();
}
if(q2.size())
{
flag2 = 1;
now2 = q2.front();
q2.pop();
}
int xx, yy;
for(int i = 0; i < 4; ++i)
{
if(flag1)
{
xx = now1.x + dx[i];
yy = now1.y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && s[xx][yy] == '#' && !vis1[xx][yy])
{
vis1[xx][yy] = 1;
nxt1.x = xx;
nxt1.y = yy;
nxt1.step = now1.step + 1;
q1.push(nxt1);
if(!vis2[xx][yy])
{
cout << "num++ 's position" << xx << ' ' << yy << '\n';
num++;
flag_front = 1;
if(num == tot)
{
flag = 1;
return nxt1.step + now2.step;
}
}
}
}
if(flag2)
{
xx = now2.x + dx[i];
yy = now2.y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && s[xx][yy] == '#' && !vis2[xx][yy])
{
vis2[xx][yy] = 1;
nxt2.x = xx;
nxt2.y = yy;
nxt2.step = now2.step + 1;
q2.push(nxt2);
if(!vis1[xx][yy])
{
cout << "num++ 's position" << xx << ' ' << yy << '\n';
num++;
if(num == tot)
{
flag = 1;
if(flag_front)
return nxt1.step + nxt2.step;
else
return now1.step + nxt2.step;
}
}
}
}
}
}
// cout << "There is not a right method!" << '\n';
// cout << "num :" << num <<'\n';
return inf;
}
int main()
{
int t;
freopen("00in.txt", "r", stdin);
cin >> t;
int tem = t;
while(t--)
{
tot = 0;
flag = 0;
ans = inf;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
cin >> s[i];
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
if(s[i][j] == '#')
{
g[tot].x = i;
g[tot].y = j;
tot++;
}
}
// cout << "Check the grass : " << '\n';
// for(int i = 0; i < tot; ++i)
// cout << g[i].x << ' ' << g[i].y << '\n';
if(tot <= 2)
{
// cout << "The number of grass is less than 3." << '\n';
if(tot > 0)
cout << "Case " << tem - t << ": 0" << '\n';
else
cout << "Case " << tem - t << ": -1" << '\n';
}
else
{
// cout << "Check the dapei : " << '\n';
for(int i = 0; i < tot; ++i)
for(int j = i + 1; j < tot; ++j)
{
cout << i << ' ' << j << '\n';
cout << "position : " << g[i].x << ' ' << g[i].y << ' ' << g[j].x << ' ' << g[j].y << '\n';
memset(vis1, 0, sizeof(vis1));
memset(vis2, 0, sizeof(vis2));
int res = bfs(g[i], g[j]);
cout << "Check the bfs : " << res << '\n';
if(res < ans)
ans = res;
}
if(flag)
cout << "Case " << tem - t << ": " << ans << '\n';
else
cout << "Case " << tem - t << ": -1" << '\n';
}
}
return 0;
}