제출 #236180

#제출 시각아이디문제언어결과실행 시간메모리
236180nicolaalexandraMecho (IOI09_mecho)C++14
100 / 100
404 ms11256 KiB
#include <bits/stdc++.h> #define DIM 810 using namespace std; char s[DIM]; int a[DIM][DIM],b[DIM][DIM],dist[DIM][DIM],f[DIM*DIM]; deque <pair<int,int> > c,aux,d; int di[] = {-1,1,0,0}; int dj[] = {0,0,-1,1}; int n,nr,i,j,xstart,ystart,xfin,yfin; inline int inmat (int i, int j){ if (i >= 1 && j >= 1 && i <= n && j <= n) return 1; return 0; } int verif (int val){ /// mai intai vad cat se extind albinele dupa val secunde c.clear(); memset (f,0,sizeof f); for (i=1;i<=n;i++) for (j=1;j<=n;j++){ b[i][j] = a[i][j]; if (a[i][j] == 1) c.push_back(make_pair(i,j)); } for (i=1;i<=val;i++){ aux.clear(); for (auto it : c){ int ic = it.first, jc = it.second; for (int dir=0;dir<=3;dir++){ int iv = ic + di[dir]; int jv = jc + dj[dir]; if (inmat (iv,jv) && b[iv][jv] == 0){ aux.push_back(make_pair(iv,jv)); b[iv][jv] = 1; }}} c = aux; f[i] = 1; } if (b[xstart][ystart]) return 0; /// d - lista cu toate locurile in care pot sa ajung pana la secunda asta memset (dist,0,sizeof dist); d.clear(); d.push_back(make_pair(xstart,ystart)); dist[xstart][ystart] = 1; while (!d.empty()){ int ic = d.front().first; int jc = d.front().second; d.pop_front(); if (dist[ic][jc] % nr == 0 && !f[dist[ic][jc] / nr + val]){ /// inseamna ca a mai trecut un minut si trb sa avansez cu albinele f[dist[ic][jc] / nr + val] = 1; aux.clear(); for (auto it : c){ int i = it.first, j = it.second; for (int dir=0;dir<=3;dir++){ int iv = i + di[dir]; int jv = j + dj[dir]; if (inmat(iv,jv) && b[iv][jv] == 0){ aux.push_back(make_pair(iv,jv)); b[iv][jv] = 1; }}} c = aux; } for (int dir=0;dir<=3;dir++){ int iv = ic + di[dir]; int jv = jc + dj[dir]; if (inmat (iv,jv) && (b[iv][jv] == 0 || b[iv][jv] == 3) && !dist[iv][jv]){ if (iv == xfin && jv == yfin) /// am reusit sa ajung return 1; dist[iv][jv] = 1 + dist[ic][jc]; d.push_back(make_pair(iv,jv)); }}} return 0; } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>nr; for (i=1;i<=n;i++){ cin>>s+1; for (j=1;j<=n;j++){ if (s[j] == 'T') a[i][j] = 2; if (s[j] == 'M'){ xstart = i, ystart = j; //a[i][j] = 4; } if (s[j] == 'D'){ xfin = i, yfin = j; a[i][j] = 3; } if (s[j] == 'H') a[i][j] = 1; } } /*for (i=1;i<=n;i++,cout<<endl) for (j=1;j<=n;j++) cout<<a[i][j]<<" "; */ int st = 0, dr = n*n, sol = -1; while (st <= dr){ int mid = (st+dr)>>1; if (verif (mid)){ sol = mid; st = mid+1; } else dr = mid-1; } cout<<sol; return 0; }

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

mecho.cpp: In function 'int main()':
mecho.cpp:96:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>>s+1;
              ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...