ABC 简单题
D 思维题
D - Grid Ice Floor
题意
给定一个 \(n \times m\) 的矩阵,矩阵每个位置上的字符要么是 '.' 要么是 '#',保证矩阵的最外围一圈都是 '#'。玩家初始位于位置 (2, 2)。玩家可以进行移动,但是移动有条件:玩家首先选定一个移动方向,之后在这个方向上一直移动,知道遇到 '#' 为止,即玩家只能移动到字符是 '.' 的位置。
问你玩家能够经过多少个位置 '.' ?
思路
刚开始的思路是搜索,但是搜索有个问题,就是可能会漏,因为每个位置是可以重复到达的,为了使得玩家可以到达尽可能多的未到达的位置。
所以除去搜索的思路,我们利用一个队列来不重地记录每次停下的位置,并再这个位置向四个方向延伸,以此来找遍所有的可达位置,同时记录答案即可。
代码
//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*
*/
const int maxm = 2e2 + 5, inf = 0x3f3f3f3f, mod = 998244353;
int n, m, ans,
fx[4] = {1, 0, -1, 0},
fy[4] = {0, -1, 0, 1};
bool vis[maxm][maxm], pos[maxm][maxm];
string ss[maxm];
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; ++ i){
cin >> ss[i];
ss[i] = 'a' + ss[i];
}
vis[2][2] = true;
queue<pii> q;
q.push({2, 2});
while(!q.empty()){
auto [x, y] = q.front();
q.pop();
if(pos[x][y]) continue;
vis[x][y] = true;
pos[x][y] = true;
int xx, yy;
for(int i = 0; i < 4; ++ i){
xx = x; yy = y;
while(1){
xx += fx[i]; yy += fy[i];
if(ss[xx][yy] == '.'){
vis[xx][yy] = true;
}else{
xx -= fx[i]; yy -= fy[i];
if(!pos[xx][yy]) q.push({xx, yy});
break;
}
}
}
}
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j){
if(vis[i][j]) ++ ans;
}
}
cout << ans << '\n';
return ;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}
- Beginner 思维 AtCoder Contest 311beginner atcoder contest 311 beginner思维atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334