『Fwb』拾放新月の题解
难度：提高+/省选−。
思路：模拟+Tarjan。
考虑哪几种情况 Fwb 必胜，剩下的就是 Awa 必胜了。
设
- 从
(1,1) 开始 BFS 预处理fwb_{i,j} 。 - 从
(n,m) 开始 BFS 预处理awa_{i,j} 。
则 Fwb 必胜一定有以下几种情况，具体每种情况的处理方法下面再讲：
- Fwb 可以先于 Awa 走到一个月亮上（这里需要声明，拾取月亮这个操作为假操作，因为直接走到月亮上不动一定比拾取了再放下更优）。“先于”，即
fwb_{i,j}<awa_{i,j} ，由于 Awa 无法走到月亮上，所以在月亮的位置 Awa 花费为无穷，所以要考虑路途中 Fwb 不会被 Awa 拦截，所以需要严格大于（具体看代码注释）。 - Fwb 可以较先于 Awa 走到一处空地（
.），且 Awa 走到此处的时间加从此处走到(\lceil{n/2}\rceil,\lceil{m/2}\rceil) 的时间> k 。“较先于”，即fwb_{i,j}\le awa_{i,j} ，由于只要走到了，哪怕被 Awa 抓住也是最大限度的消耗了时间（且获胜），所以只要较先于即可。 - Fwb、Awa、地图中心三点有任意两点不连通。对于 Fwb 和地图中心的连通定义为没有
#阻隔，剩余两组定义为没有#和@阻隔（为了便于代码实现，代码判断稍有不同，具体看代码注释）。 - 存在
.组成的环且 Fwb 先于 Awa 走到环上任意一点。由于 Awa 也可以走到.的位置，所以必须严格先于。
除以上情况之外，Awa 必胜。
注：判断先于和较先于时需要预处理。记得沿途的每一个位置都需要满足先于或较先于的条件，以免出现中断。
所谓中断，即指预处理出来的数组不连通。具体实现看代码注释。
第一种情况可以直接循环判断解决，第二种情况可以先从地图中心出发预处理出每个点到地图中心的最短距离，再循环判断解决。
第三种情况可以在第二种情况求最短路时用
第四种情况处理起来较为困难。我们首先找到 Fwb、Awa、地图中心组成的连通块，然后以 . 的位置建无向图 *。使用 Tarjan 缩点找到所有环，在出栈的时候判断 Fwb 是否能严格先于 Awa 走到此处即可。Tarjan 不会的看这里。
*说明：
Q：为什么 @ 的地方不建图？
A：因为如果 Fwb 能走到 @ 处，则在情况一就被判断了，所以再次判断没有意义。
具体处理时还会有一些细节，代码做了详细的注释，供各位食用。
代码略长，稍安勿躁。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int dxy[4][4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
const int N = 1100;
int n, m, k;
char mp[N][N];
int fwb[N][N], awa[N][N], vis[N][N], can[N][N];
vector<int> e[N * N];
int dfn[N * N], low[N * N], id, really_can[N][N];
stack<int> st;
int zhong[N][N];
struct node {
int x, y;
int step;
};
void init() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
fwb[i][j] = 1e9;
awa[i][j] = 1e9;
zhong[i][j] = 1e9;
}
}
}
void bfsfwb() {
queue<node> q;
node t;
t.x = 1, t.y = 1;
t.step = 0;
q.push(t);
while (!q.empty()) {
node f = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int dx = dxy[i][0] + f.x, dy = dxy[i][1] + f.y;
if (dx >= 1 && dx <= n && dy >= 1 && dy <= m) {
if (!vis[dx][dy] && mp[dx][dy] != '#') {
vis[dx][dy] = 1;
fwb[dx][dy] = f.step + 1;
node t;
t.x = dx, t.y = dy;
t.step = f.step + 1;
q.push(t);
}
}
}
}
}
void bfsawa() {
queue<node> q;
node t;
t.x = n, t.y = m;
t.step = 0;
q.push(t);
while (!q.empty()) {
node f = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int dx = dxy[i][0] + f.x, dy = dxy[i][1] + f.y;
if (dx >= 1 && dx <= n && dy >= 1 && dy <= m) {
if (!vis[dx][dy] && mp[dx][dy] == '.') {
vis[dx][dy] = 1;
awa[dx][dy] = f.step + 1;
node t;
t.x = dx, t.y = dy;
t.step = f.step + 1;
q.push(t);
}
}
}
}
}
void bfs(int tx, int ty) {//判断fwb可去往的点，全代码最难的一个部分
queue<node> q;
node t;
t.x = tx, t.y = ty;
t.step = 0;
q.push(t);
while (!q.empty()) {
node f = q.front();
q.pop();
if (fwb[f.x][f.y] <= awa[f.x][f.y]) {//可以较早到达，用于追逐处(find)
//为了方便理解，这里加了 if，实则可以省去
can[f.x][f.y] = 1;
}
for (int i = 0; i < 4; i++) {
int dx = dxy[i][0] + f.x, dy = dxy[i][1] + f.y;
if (dx >= 1 && dx <= n && dy >= 1 && dy <= m) {
if (!vis[dx][dy] && mp[dx][dy] != '#' && fwb[f.x][f.y] < awa[f.x][f.y]) {
//一路上都只能走能去往的点，以免路上不能走到，但最终的点可以走到，使得 WA。
//当然，这只是一个保险操作，但是有了总比没有好
//上面的f.x，f.y 不属于错误，因为每次判断上一次，和每次判断当前是一个效果
vis[dx][dy] = 1;
node t;
t.x = dx, t.y = dy;
t.step = 0;
q.push(t);
}
}
}
}
}
void bfs_(int tx, int ty) {//判断fwb可去往的点，全代码最难的一个部分
queue<node> q;
node t;
t.x = tx, t.y = ty;
t.step = 0;
q.push(t);
while (!q.empty()) {
node f = q.front();
q.pop();
if (fwb[f.x][f.y] < awa[f.x][f.y]) {//用于判环处(tarjan)和月亮(pan)
//由于走到环里必须先于 Awa 到，所以需要判断
really_can[f.x][f.y] = 1;
}
for (int i = 0; i < 4; i++) {
int dx = dxy[i][0] + f.x, dy = dxy[i][1] + f.y;
if (dx >= 1 && dx <= n && dy >= 1 && dy <= m) {
if (!vis[dx][dy] && mp[dx][dy] != '#' && fwb[f.x][f.y] < awa[f.x][f.y]) {
//一路上都只能走能去往的点，以免路上不能走到，但最终的点可以走到，使得 WA。
//当然，这只是一个保险操作，但是有了总比没有好
vis[dx][dy] = 1;
node t;
t.x = dx, t.y = dy;
t.step = 0;
q.push(t);
}
}
}
}
}
void pan() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '@' && really_can[i][j]) {//这个点是月亮且可以早到达
//虽然理论上是较早到达即可，但是由于考虑到路上被拦住的情况，必须是严格早于
printf("Fwb Win!");
exit(0);
}
}
}
}
void bfszhong(int x, int y) {//查询从中心出发到每个点的最短路
queue<node> q;
node t;
t.x = x, t.y = y;
t.step = 0;
q.push(t);
while (!q.empty()) {
node f = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int dx = dxy[i][0] + f.x, dy = dxy[i][1] + f.y;
if (dx >= 1 && dx <= n && dy >= 1 && dy <= m) {
if (!vis[dx][dy] && mp[dx][dy] == '.') {
//从中央开始走是 Awa 的路，不可穿越月亮
vis[dx][dy] = 1;
zhong[dx][dy] = f.step + 1;
node t;
t.x = dx, t.y = dy;
t.step = f.step + 1;
q.push(t);
}
}
}
}
}
void find(int x, int y) {
if (mp[x][y] != '@' && can[x][y] && awa[x][y] + zhong[x][y] > k) {
/*可以较早到达且被带走需要的时常超过总时长
注意此处必须判断不为月亮，因为如果是月亮那就必须是严格早于
但没有在pan中结束，说明Fwb无法走到这个月亮来，此时awa是无穷值，会导致WA
*/
printf("Fwb Win!");
exit(0);
}
for (int i = 0; i < 4; i++) {
int dx = dxy[i][0] + x, dy = dxy[i][1] + y;
if (dx >= 1 && dx <= n && dy >= 1 && dy <= m) {
if (!vis[dx][dy] && mp[dx][dy] != '#') {
/*
这里与我们前面讲的不同的是，
月亮也能走，因为如果有月亮的阻挡隔开，会在计算zhong时取无穷大，则Fwb必胜
但其实的思想还是我们前面讲的那样，只是在写代码的时候为了简洁而简化了
*/
vis[dx][dy] = 1;
find(dx, dy);
}
}
}
}
inline int get(int x, int y) {//将坐标换成点，(x,y)-->z
return m * (x - 1) + y;
}
void get_map(int x, int y) {
for (int i = 0; i < 4; i++) {
int dx = dxy[i][0] + x, dy = dxy[i][1] + y;
if (dx >= 1 && dx <= n && dy >= 1 && dy <= m) {
if (mp[dx][dy] == '.') {//只要是 . 就是通路，就需要建无向图
e[get(x, y)].push_back(get(dx, dy));
e[get(dx, dy)].push_back(get(x, y));
}
if (!vis[dx][dy] && mp[dx][dy] == '.') {
vis[dx][dy] = 1;
get_map(dx, dy);
}
}
}
}
pair<int, int> rev(int x) {//将点换回坐标 z-->(x,y)
pair<int, int> t;
t.first = x / m;
t.second = x % m;
if (t.second > 0) t.first++;
else t.second = m;
return t;
}
void tarjan(int u, int fa) {
dfn[u] = ++id;
low[u] = id;
st.push(u);
for (int v : e[u]) {
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
} else if (v != fa) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {//tarjan缩点的简化应用
int t, shu = 0, flag = 0;
do {
t = st.top();
st.pop();
pair<int, int> re = rev(t);
if (really_can[re.first][re.second]) {//可以提前到达
flag = 1;
}
shu++;
} while(t != u);
if (shu >= 4 && flag) {//至少要有超过 4 个点（最小环）的连通分量
printf("Fwb Win!");
exit(0);
}
}
}
signed main() {
scanf("%lld%lld%lld", &n, &m, &k);
init();
for (int i = 1; i <= n; i++) {
scanf("%s", mp[i] + 1);
}
vis[1][1] = 1;
fwb[1][1] = 0;
bfsfwb();//求fwb最短路
memset(vis, 0, sizeof(vis));
vis[n][m] = 1;
awa[n][m] = 0;
bfsawa();//求awa最短路
memset(vis, 0, sizeof(vis));
vis[1][1] = 1;
bfs(1, 1);
memset(vis, 0, sizeof(vis));
vis[1][1] = 1;
bfs_(1, 1);
pan();
int zx = ceil(1.0 * n / 2.0), zy = ceil(1.0 * m / 2.0);//中心坐标
memset(vis, 0, sizeof(vis));
vis[zx][zy] = 1;
zhong[zx][zy] = 0;
bfszhong(zx, zy);
memset(vis, 0, sizeof(vis));
vis[zx][zy] = 1;
find(zx, zy);
if (!vis[1][1] || !vis[n][m]) {//Fwb和Awa必须联通，否则 Fwb 必胜
printf("Fwb Win!");
return 0;
}
memset(vis, 0, sizeof(vis));
vis[1][1] = 1;
get_map(1, 1);
tarjan(1, -1);
printf("Awa Win!");
return 0;
}我的代码很长，但是比较好理解，适合第一遍写，这里附上验题人代码，简洁许多：
#include<bits/stdc++.h>
using namespace std;
int n,m,t,v[1003][1003][3],zl[1003][1003],dl[1000006][2],inf=99999999,z[1000006][2][3],l,r,vis[1003][1003],xj[5]={1,0,-1,0,0},yj[5]={0,1,0,-1,0},LOW[1000006],DNS[1000006],tot,id[1003][1003],zh[1000006],rr;
string s;
void tarjan(int d,int f){
DNS[d]=LOW[d]=++tot;
zh[++rr]=d;
int ll=rr;
int x=(d-1)/m+1,y=(d-1)%m+1;
for (int i=0;i<=3;i++){
if (zl[x+xj[i]][y+yj[i]]&&(x+xj[i]-1)*m+y+yj[i]!=f){
if (!DNS[(x+xj[i]-1)*m+y+yj[i]]){
tarjan((x+xj[i]-1)*m+y+yj[i],d);
LOW[d]=min(LOW[d],LOW[(x+xj[i]-1)*m+y+yj[i]]);
}
else LOW[d]=min(LOW[d],DNS[(x+xj[i]-1)*m+y+yj[i]]);
}
}
if (DNS[d]==LOW[d]){
if (ll!=rr){
for (int i=ll;i<=rr;i++){
id[(zh[i]-1)/m+1][(zh[i]-1)%m+1]=1;
}
}
rr=ll-1;
}
}
int main(){
cin>>n>>m>>t;
for (int i=1;i<=n;i++){
cin>>s;
for (int j=1;j<=m;j++){
if (s[j-1]=='.') zl[i][j]=1;
if (s[j-1]=='@') zl[i][j]=2;
v[i][j][0]=v[i][j][1]=v[i][j][2]=vis[i][j]=inf;
}
}
v[1][1][0]=v[n][m][1]=v[(n+1)/2][(m+1)/2][2]=0;
z[1][0][0]=z[1][1][0]=1;
z[1][0][1]=n;
z[1][1][1]=m;
z[1][0][2]=(n+1)/2;
z[1][1][2]=(m+1)/2;
for (int ii=0;ii<=2;ii++){
l=r=1;
while(l<=r){
int x=z[l][0][ii],y=z[l][1][ii];
for (int j=0;j<=3;j++){
if ((zl[x+xj[j]][y+yj[j]]==1||(zl[x+xj[j]][y+yj[j]]==2&&!ii))&&vis[x+xj[j]][y+yj[j]]!=ii){
v[x+xj[j]][y+yj[j]][ii]=v[x][y][ii]+1;
z[++r][0][ii]=x+xj[j];
z[r][1][ii]=y+yj[j];
vis[x+xj[j]][y+yj[j]]=ii;
}
}
l++;
}
}
tarjan(1,0);
l=r=dl[1][0]=dl[1][1]=1;
while(l<=r){
int x=dl[l][0],y=dl[l][1];
if (id[x][y]){
cout<<"Fwb Win!";
return 0;
}
for (int j=0;j<=4;j++){
if (zl[x+xj[j]][y+yj[j]]==2){
cout<<"Fwb Win!";
return 0;
}
if (zl[x+xj[j]][y+yj[j]]&&vis[x+xj[j]][y+yj[j]]!=6&&v[x+xj[j]][y+yj[j]][0]<v[x+xj[j]][y+yj[j]][1]){
dl[++r][0]=x+xj[j];
dl[r][1]=y+yj[j];
vis[x+xj[j]][y+yj[j]]=6;
}
if (v[x+xj[j]][y+yj[j]][0]<=v[x+xj[j]][y+yj[j]][1]&&v[x][y][1]+v[x][y][2]>t){
cout<<"Fwb Win!";
return 0;
}
}
l++;
}
cout<<"Awa Win!";
}#include<bits/stdc++.h>
using namespace std;
const int QAQ=1100;
bool vis[QAQ*QAQ*4];
char a[QAQ][QAQ],she[QAQ*QAQ];
int n,m,k,dis[QAQ*QAQ],mi=2e9,ju[QAQ*QAQ],cnt,zhan[QAQ*QAQ],li[QAQ*QAQ],ju2[QAQ*QAQ],
dfn[QAQ*QAQ],low[QAQ*QAQ],top,nex[QAQ*QAQ*4],to[QAQ*QAQ*4],head[QAQ*QAQ];
int id(int x,int y) {return (x-1)*m+y;}
queue<int> dui;
vector<int> dian[QAQ*QAQ],kong;
vector<vector<int> > ans;
void add(int u,int v) {nex[++cnt]=head[u],to[cnt]=v,head[u]=cnt;}
void tajian(int u)
{
dfn[u]=++cnt;low[u]=cnt;
zhan[++top]=u;
for(int i=head[u],v;i;i=nex[i])
{
if(vis[i^1]) continue; vis[i]=1;
v=to[i];
if(!dfn[v]) tajian(v),low[u]=min(low[u],low[v]);
else low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
vector<int> x=kong;
while(zhan[top]!=u) x.push_back(zhan[top--]);
x.push_back(zhan[top--]);
ans.push_back(x);
}
}
void yu()
{
dui.push(id(n,m));dis[id(n,m)]=0;vis[id(n,m)]=1;
while(!dui.empty())
{
int nw=dui.front();dui.pop();
for(int i=0;i<(int)dian[nw].size();i++)
{
int v=dian[nw][i];
if(!vis[v]&&she[v]!='@') dis[v]=dis[nw]+1,dui.push(v),vis[v]=1;
}
}
for(int i=1;i<=n*m;i++) vis[i]=0,ju[i]=2e9;
dui.push(id(1,1));ju[id(1,1)]=0;vis[id(1,1)]=1;
while(!dui.empty())
{
int nw=dui.front();dui.pop();
for(int i=0;i<(int)dian[nw].size();i++)
{
int v=dian[nw][i];
if(!vis[v]) ju[v]=ju[nw]+1,vis[v]=1,dui.push(v);
}
}
for(int i=1;i<=n*m;i++) vis[i]=0,ju2[i]=2e9;
dui.push(id(1,1));ju2[id(1,1)]=0;vis[id(1,1)]=1;
while(!dui.empty())
{
int nw=dui.front();dui.pop();
for(int i=0;i<(int)dian[nw].size();i++)
{
int v=dian[nw][i];
if(!vis[v]&&(she[v]!='@')) ju2[v]=ju2[nw]+1,vis[v]=1,dui.push(v);
}
}
for(int i=1;i<=n*m;i++) vis[i]=0,li[i]=2e9;
dui.push(id(n/2+n%2,m/2+m%2));li[id(n/2+n%2,m/2+m%2)]=0;vis[id(n/2+n%2,m/2+m%2)]=1;
while(!dui.empty())
{
int nw=dui.front();dui.pop();
for(int i=0;i<(int)dian[nw].size();i++)
{
int v=dian[nw][i];
if(!vis[v]&&she[v]!='@') li[v]=li[nw]+1,dui.push(v),vis[v]=1;
}
}
}
signed main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j],dis[id(i,j)]=2e9,she[id(i,j)]=a[i][j];
cnt=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(she[id(i,j)]!='#')
{
if(i<n&&she[id(i+1,j)]!='#')
dian[id(i,j)].push_back(id(i+1,j)),add(id(i,j),id(i+1,j)),
dian[id(i+1,j)].push_back(id(i,j)),add(id(i+1,j),id(i,j));
if(j<m&&she[id(i,j+1)]!='#')
dian[id(i,j)].push_back(id(i,j+1)),add(id(i,j),id(i,j+1)),
dian[id(i,j+1)].push_back(id(i,j)),add(id(i,j+1),id(i,j));
}
cnt=0,yu(),cnt=0;
for(int i=0;i<=n*m*4;i++) vis[i]=0;
tajian(id(1,1));
// for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!dfn[id(i,j)]) tajian(id(i,j));
for(int i=0;i<(int)ans.size();i++)
if(ans[i].size()>=3)
{
int x=ans[i][(int)ans[i].size()-1];
if(ju[x]<2e8&&dis[x]<2e8) if(ju[x]<dis[x]) return puts("Fwb Win!"),0;
}
// cout<<"dfasdsdsdsdsds";
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ju2[id(i,j)]<2e8&&dis[id(i,j)]>2e8) return puts("Fwb Win!"),0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(she[id(i,j)]=='@')
for(int k=0;k<(int)dian[id(i,j)].size();k++)
{
int v=dian[id(i,j)][k];
if(ju2[v]<2e8&&dis[v]<2e8) if(ju2[v]<dis[v]) return puts("Fwb Win!"),0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ju[id(i,j)]<2e8&&dis[id(i,j)]<2e8)
if(ju[id(i,j)]<=dis[id(i,j)])
if(dis[id(i,j)]+li[id(i,j)]>k) return puts("Fwb Win!"),0;
puts("Awa Win!");
return 0;
}