제출 #916016

#제출 시각아이디문제언어결과실행 시간메모리
916016gaga999Mecho (IOI09_mecho)C++17
100 / 100
282 ms2772 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("Ofast") #define SIZE 805 #define all(x) x.begin(), x.end() #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; int n, mxstep; char a[SIZE][SIZE]; bool vis[SIZE][SIZE]; bool bee[SIZE][SIZE]; struct node { int x, y; int s; bool operator ==(node b) { return x==b.x && y==b.y; } }; vector<node> hive; node start; node endpo; int dx[]={-1, 1, 0, 0}; int dy[]={0, 0, -1, 1}; bool bfs(int wait) { queue<node> q; // bear q.push(start); queue<node> Q; // bee memset(vis, 0, sizeof(vis)); memset(bee, 0, sizeof(bee)); vis[start.x][start.y]=1; for(node t:hive) { bee[t.x][t.y]=1; Q.push(t); } // 吃蜜时间蜜蜂围攻 while(!Q.empty() && Q.front().s<wait) { node w=Q.front(); Q.pop(); int i=w.x, j=w.y; for(int k=0; k<4; k++) { int ni=i+dx[k]; int nj=j+dy[k]; // 不越界 if(ni<0 || ni>=n || nj<0 || nj>=n) continue; // 不走回头路 if(bee[ni][nj]) continue; // 不入禁区 if(a[ni][nj]=='D' || a[ni][nj]=='T') continue; bee[ni][nj]=1; Q.push({ni, nj, w.s+1}); } } // 原始位置已被攻占 if(bee[start.x][start.y]) return 0; int steps=1; // 行走的次数 while(!q.empty()) { // 小熊先走 while(!q.empty() && q.front().s<steps*mxstep) { node w=q.front(); q.pop(); int i=w.x, j=w.y; if(w==endpo) return 1; if(bee[i][j]) continue; for(int k=0; k<4; k++) { int ni=i+dx[k]; int nj=j+dy[k]; // 不越界 if(ni<0 || ni>=n || nj<0 || nj>=n) continue; // 不被蜜蜂蛰 if(bee[ni][nj]) continue; // 不走回头路 if(vis[ni][nj]) continue; // 不入禁区 if(a[ni][nj]=='T') continue; vis[ni][nj]=1; q.push({ni, nj, w.s+1}); } } // 蜜蜂后走 while(!Q.empty() && Q.front().s<wait+steps) { node w=Q.front(); Q.pop(); int i=w.x, j=w.y; for(int k=0; k<4; k++) { int ni=i+dx[k]; int nj=j+dy[k]; // 不越界 if(ni<0 || ni>=n || nj<0 || nj>=n) continue; // 不走回头路 if(bee[ni][nj]) continue; // 不入禁区 if(a[ni][nj]=='D' || a[ni][nj]=='T') continue; bee[ni][nj]=1; Q.push({ni, nj, w.s+1}); } } steps++; } return 0; } signed main() { cin>>n>>mxstep; int si, sj; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { cin>>a[i][j]; if(a[i][j]=='H') hive.push_back({i, j, 0}); if(a[i][j]=='M') start={i, j, 0}; if(a[i][j]=='D') endpo={i, j, 0}; } int l=0, r=n*n; int ans=-1; while(l<=r) { int m=(l+r)>>1; if(bfs(m)) { ans=m; l=m+1; } else r=m-1; } cout<<ans; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'int main()':
mecho.cpp:126:6: warning: unused variable 'si' [-Wunused-variable]
  126 |  int si, sj;
      |      ^~
mecho.cpp:126:10: warning: unused variable 'sj' [-Wunused-variable]
  126 |  int si, sj;
      |          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...