結果
問題 | No.2412 YOU Grow Bigger! |
ユーザー |
|
提出日時 | 2023-08-11 22:06:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 226 ms / 6,000 ms |
コード長 | 1,513 bytes |
コンパイル時間 | 2,130 ms |
コンパイル使用メモリ | 201,440 KB |
最終ジャッジ日時 | 2025-02-16 01:27:39 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; using pii=pair<int,int>; #define all(a) a.begin(),a.end() #define pb push_back #define sz(a) ((int)a.size()) const int N=2405; int n,m,b[N][N]; string a[N]; bool vis[N][N]; bool valid(int i, int j){return i>=0&&i<n&&j>=0&&j<m;} bool bfs(){ for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) vis[i][j]=0; queue<pii> q; q.push({1,1}),vis[1][1]=1; while(!q.empty()){ auto [x,y]=q.front(); q.pop(); for(int i: {-1,0,1}) for(int j: {-1,0,1}){ int nx=x+i,ny=y+j; if(valid(nx,ny)&&b[nx][ny]==0&&!vis[nx][ny]){ q.push({nx,ny}),vis[nx][ny]=1; } } } return vis[n-2][m-2]; } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); cin >> n >> m; for(int i=0; i<n; ++i) cin >> a[i]; for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) if(a[i][j]=='#'){ for(int x: {-1,0,1}) for(int y: {-1,0,1}) if(valid(i+x,j+y)) b[i+x][j+y]++; } for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) if(i==0||i==n-1||j==0||j==m-1) b[i][j]++; if(!bfs()){ cout << "0\n"; return 0; } for(int i=0; i<n; ++i) for(int j=0; j<m; ++j){ for(int x: {-1,0,1}) for(int y: {-1,0,1}) if(valid(i+x,j+y)) b[i+x][j+y]++; if(b[1][1]==0&&b[n-2][m-2]==0&&!bfs()){ cout << "1\n"; return 0; } for(int x: {-1,0,1}) for(int y: {-1,0,1}) if(valid(i+x,j+y)) b[i+x][j+y]--; } cout << "2\n"; }