P7185 [CRCI2008-2009] CIJEVI题解

FindFar · 2024-09-28 23:00:04 · 题解

P7185 [CRCI2008-2009] CIJEVI

题意描述

给定一个 R \times C 的图形，给定唯一的终点和起点。

有一条通道，在其中有一个 被删去 的节点，你需要找到这个节点并输出它的位置和种类。

没有冗余节点。

输入将保证解决方案存在并且是唯一的。

方法&代码

Solution 1

看到这个题，我们很容易将其联想到一个大模拟。题目中的限制很多，数据范围也是很小的，所以可以直接模拟，好的代码很多，试着去看一看。

Solution 2

相信某些同学像我一样，学会了第一种方法又想要第二种方法（实际上是因为第一种方法太难而被劝退），于是这里就有了第二种清晰易懂的方法。

在平常的解法中，我们都是依照 dfs/bfs 进行搜索来找到断点，并根据断点前后情况进行对断点的状态选择。

那我们不妨换个方式来找断点。

断点一定是存在于图上的，而且由题意可以得出来 有且仅有一个 断点。

于是我们就可以通过遍历整张图的方式，找到们一个断点。

空间复杂度不够怎么办？

我们观察到， 1 \le R,C \le 25 。数据量远没有想象中的那么大。于是就可以开心地写代码了！

代码如下：

#include<bits/stdc++.h>
using namespace std;

int n,m;
char c[1005][1005];

bool l(int x,int j) {//判断左侧是否开口
    return j>1&&(c[x][j-1]=='-'||c[x][j-1]=='1'||c[x][j-1]=='2'||c[x][j-1]=='+');
}
bool r(int x,int j) {//判断右侧是否开口
    return j<n&&(c[x][j+1]=='-'||c[x][j+1]=='3'||c[x][j+1]=='4'||c[x][j+1]=='+');
}
bool u(int x,int j) {//判断上侧是否开口
    return x>1&&(c[x-1][j]=='|'||c[x-1][j]=='1'||c[x-1][j]=='4'||c[x-1][j]=='+');
}
bool d(int x,int j) {//判断下侧是否开口
    return x<n&&(c[x+1][j]=='|'||c[x+1][j]=='2'||c[x+1][j]=='3'||c[x+1][j]=='+');
}

int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>c[i][j];
        }
    }

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(c[i][j]!='.')continue;
            else if(l(i,j)&&r(i,j)&&u(i,j)&&d(i,j)) {//+
                cout<<i<<' '<<j<<' '<<'+';
                return 0;
            } else if(l(i,j)&&r(i,j)) {//-
                cout<<i<<' '<<j<<' '<<'-';
                return 0;
            } else if(u(i,j)&&d(i,j)) {//|
                cout<<i<<' '<<j<<' '<<'|';
                return 0;
            } else if(r(i,j)&&d(i,j)) {//1
                cout<<i<<' '<<j<<' '<<'1';
                return 0;
            } else if(r(i,j)&&u(i,j)) {//2
                cout<<i<<' '<<j<<' '<<'2';
                return 0;
            } else if(l(i,j)&&u(i,j)) {//3
                cout<<i<<' '<<j<<' '<<'3';
                return 0;
            } else if(l(i,j)&&d(i,j)) {//4
                cout<<i<<' '<<j<<' '<<'4';
                return 0;
            }
        }
    }
    return 0;
}

HACK

你在写完这个代码提交上去之后，是不是错了两个点？

原因还是要归结到它们身上：

4 3
..1.
..|M
Z-3.

1 3
M.Z

它们有一个共同的特点，就是在起点或终点前是断点。在你没有进行对起点和终点的特判时，你就会出错。

你可以将那 4 个判断函数改成这个样子，就可以通过这个hack了。

bool l(int x, int j) {
    return j > 1 && (c[x][j - 1] == '-' || c[x][j - 1] == '1' || c[x][j - 1] == '2' || c[x][j - 1] == '+' || c[x ][j - 1] == 'M' || c[x ][j - 1] == 'Z');
}
bool r(int x, int j) {
    return j < m&&(c[x][j + 1] == '-' || c[x][j + 1] == '3' || c[x][j + 1] == '4' || c[x][j + 1] == '+' || c[x ][j + 1] == 'M' || c[x ][j + 1] == 'Z');
}
bool u(int x, int j) {
    return x > 1 && (c[x - 1][j] == '|' || c[x - 1][j] == '1' || c[x - 1][j] == '4' || c[x - 1][j] == '+' || c[x - 1][j ] == 'M' || c[x - 1][j ] == 'Z');
}
bool d(int x, int j) {
    return x < n&&(c[x + 1][j] == '|' || c[x + 1][j] == '2' || c[x + 1][j] == '3' || c[x + 1][j] == '+' || c[x + 1][j ] == 'M' || c[x + 1][j ] == 'Z');
}

在这个判断中，我实际上将起点和终点看做了 '+' 这个符号，进行了特判。这样就可以避免了hack数据的错误。

感谢阅读。（第四篇题解）