제출 #1084605

#제출 시각아이디문제언어결과실행 시간메모리
1084605kiethm07Mecho (IOI09_mecho)C++11
4 / 100
708 ms12024 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define iii pair<int,pii> #define fi first #define se second #define vi vector<int> #define vii vector<pii> #define pb(i) push_back(i) #define all(x) x.begin(),x.end() #define TEXT "a" using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int inf = 1e9 + 7; const ld eps = 1e-8; const double pi = acos(-1); const int N = 805; int n,s; int f[N][N], g[N][N]; char a[N][N]; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; bool check(int val){ queue<pii> q; memset(f,-1,sizeof(f)); memset(g,-1,sizeof(g)); pii M, D; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ if (a[i][j] == 'M') M = pii(i,j); if (a[i][j] == 'D') D = pii(i,j); if (a[i][j] == 'H'){ q.push(pii(i,j)); f[i][j] = 0; } } } while(!q.empty()){ pii u = q.front(); q.pop(); if (f[u.fi][u.se] >= val) continue; for (int i = 0; i < 4; i++){ int x = u.fi + dx[i]; int y = u.se + dy[i]; if (x == 0 || x > n || y == 0 || y > n) continue; if (a[x][y] == 'T' || a[x][y] == 'D') continue; if (f[x][y] != -1) continue; f[x][y] = f[u.fi][u.se] + 1; q.push(pii(x,y)); } } for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++){ if (f[i][j] == -1) continue; f[i][j] = 0; q.push(pii(i,j)); } } while(!q.empty()){ pii u = q.front(); q.pop(); for (int i = 0; i < 4; i++){ int x = u.fi + dx[i]; int y = u.se + dy[i]; if (x == 0 || x > n || y == 0 || y > n) continue; if (a[x][y] == 'T' || a[x][y] == 'D') continue; if (f[x][y] != -1) continue; f[x][y] = f[u.fi][u.se] + s; q.push(pii(x,y)); } } f[D.fi][D.se] = inf; g[M.fi][M.se] = 0; if (f[M.fi][M.se] != -1) return 0; q.push(M); while(!q.empty()){ pii u = q.front(); q.pop(); for (int i = 0; i < 4; i++){ int x = u.fi + dx[i]; int y = u.se + dy[i]; if (x == 0 || x > n || y == 0 || y > n) continue; if (a[x][y] == 'T') continue; if (g[x][y] != -1) continue; if (f[x][y] <= g[u.fi][u.se] + 1) continue; g[x][y] = g[u.fi][u.se] + 1; q.push(pii(x,y)); } } return g[D.fi][D.se] != -1; } int main(){ cin.tie(0) -> sync_with_stdio(0); if (fopen(TEXT".inp","r")){ freopen(TEXT".inp","r",stdin); freopen(TEXT".out","w",stdout); } cin >> n >> s; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++) cin >> a[i][j]; } int res = -1; int l = 0; int r = inf; // cout << check(2) << "\n"; // for (int i = 1; i <= n; i++){ // for (int j = 1; j <= n; j++){ // cout << f[i][j] << " "; // } // cout << "\n"; // } while(l <= r){ int mid = (l + r) / 2; if (check(mid)){ res = mid; l = mid + 1; } else r = mid - 1; } cout << res << "\n"; return 0; }

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

mecho.cpp: In function 'int main()':
mecho.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(TEXT".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(TEXT".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...