Submission #3402039
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define int long long #define rep(i,s,n) for(int i = s;i<n;i++) #define repe(i,s,n) for(int i = s;i<=n;i++) #define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--) #define all(v) (v).begin(),(v).end() #define pb push_back #define fi first #define se second typedef long long ll; typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; typedef pair<pint,int> P1; typedef pair<int,pint> P2; static const ll maxLL = (ll)1 << 62; const ll MOD=1000000007; const ll INF=1e18; int dy[]={-1,0,1,0}; int dx[]={0,1,0,-1}; int sx,sy,gx,gy,h,w,t; char m[10][10]; int d[10][10]; int bfs(int x){ rep(i,0,h)rep(j,0,w)d[i][j]=INF; queue<pint> que; que.push(pint(sy,sx)); d[sy][sx]=0; while(!que.empty()){ pint p=que.front();que.pop(); rep(i,0,4){ int ny=p.fi+dy[i]; int nx=p.se+dx[i]; int ss; if(m[ny][nx]=='#')ss=x; else ss=1; if(d[ny][nx]>ss+d[p.fi][p.se]&&0<=nx&&nx<w&&0<=ny&&ny<h){ d[ny][nx]=ss+d[p.fi][p.se]; que.push(pint(ny,nx)); } } } return t>=d[gy][gx]; } signed main(){ cin.tie(0); ios::sync_with_stdio(false); cin>>h>>w>>t; string s; rep(i,0,h){ rep(j,0,w){ cin>>m[i][j]; } } rep(i,0,h){ rep(j,0,w){ if(m[i][j]=='S'){ sy=i; sx=j; } else if(m[i][j]=='G'){ gy=i; gx=j; } } } int lo=1,hi=t,m; while(hi-lo>1){ int m=(lo+hi)/2; if(bfs(m))lo=m; else hi=m; } cout<<lo<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 壁抜け |
User | chocopuu |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1852 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 40 / 40 | 30 / 30 | 30 / 30 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt |
Subtask1 | subtask0_sample_01.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt |
Subtask2 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt |
Subtask3 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask3_41.txt, subtask3_42.txt, subtask3_43.txt, subtask3_44.txt, subtask3_45.txt, subtask3_46.txt, subtask3_47.txt, subtask3_48.txt, subtask3_49.txt, subtask3_50.txt, subtask3_51.txt, subtask3_52.txt, subtask3_53.txt, subtask3_54.txt, subtask3_55.txt, subtask3_56.txt, subtask3_57.txt, subtask3_58.txt, subtask3_59.txt, subtask3_60.txt, subtask3_61.txt, subtask3_62.txt, subtask3_63.txt, subtask3_64.txt, subtask3_65.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 1 ms | 256 KB |
subtask0_sample_02.txt | AC | 1 ms | 256 KB |
subtask0_sample_03.txt | AC | 1 ms | 256 KB |
subtask1_01.txt | AC | 1 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | AC | 1 ms | 256 KB |
subtask1_04.txt | AC | 1 ms | 256 KB |
subtask1_05.txt | AC | 1 ms | 256 KB |
subtask1_06.txt | AC | 1 ms | 256 KB |
subtask1_07.txt | AC | 1 ms | 256 KB |
subtask1_08.txt | AC | 1 ms | 256 KB |
subtask1_09.txt | AC | 1 ms | 256 KB |
subtask1_10.txt | AC | 1 ms | 256 KB |
subtask1_11.txt | AC | 1 ms | 256 KB |
subtask1_12.txt | AC | 1 ms | 256 KB |
subtask1_13.txt | AC | 1 ms | 256 KB |
subtask1_14.txt | AC | 1 ms | 256 KB |
subtask1_15.txt | AC | 1 ms | 256 KB |
subtask2_16.txt | AC | 1 ms | 256 KB |
subtask2_17.txt | AC | 1 ms | 256 KB |
subtask2_18.txt | AC | 1 ms | 256 KB |
subtask2_19.txt | AC | 1 ms | 256 KB |
subtask2_20.txt | AC | 1 ms | 256 KB |
subtask2_21.txt | AC | 1 ms | 256 KB |
subtask2_22.txt | AC | 1 ms | 256 KB |
subtask2_23.txt | AC | 1 ms | 256 KB |
subtask2_24.txt | AC | 1 ms | 256 KB |
subtask2_25.txt | AC | 1 ms | 256 KB |
subtask2_26.txt | AC | 1 ms | 256 KB |
subtask2_27.txt | AC | 1 ms | 256 KB |
subtask2_28.txt | AC | 1 ms | 256 KB |
subtask2_29.txt | AC | 1 ms | 256 KB |
subtask2_30.txt | AC | 1 ms | 256 KB |
subtask2_31.txt | AC | 1 ms | 256 KB |
subtask2_32.txt | AC | 1 ms | 256 KB |
subtask2_33.txt | AC | 1 ms | 256 KB |
subtask2_34.txt | AC | 1 ms | 256 KB |
subtask2_35.txt | AC | 1 ms | 256 KB |
subtask2_36.txt | AC | 1 ms | 256 KB |
subtask2_37.txt | AC | 1 ms | 256 KB |
subtask2_38.txt | AC | 1 ms | 256 KB |
subtask2_39.txt | AC | 1 ms | 256 KB |
subtask2_40.txt | AC | 1 ms | 256 KB |
subtask3_41.txt | AC | 1 ms | 256 KB |
subtask3_42.txt | AC | 1 ms | 256 KB |
subtask3_43.txt | AC | 1 ms | 256 KB |
subtask3_44.txt | AC | 1 ms | 256 KB |
subtask3_45.txt | AC | 1 ms | 256 KB |
subtask3_46.txt | AC | 1 ms | 256 KB |
subtask3_47.txt | AC | 1 ms | 256 KB |
subtask3_48.txt | AC | 1 ms | 256 KB |
subtask3_49.txt | AC | 1 ms | 256 KB |
subtask3_50.txt | AC | 1 ms | 256 KB |
subtask3_51.txt | AC | 1 ms | 256 KB |
subtask3_52.txt | AC | 1 ms | 256 KB |
subtask3_53.txt | AC | 1 ms | 256 KB |
subtask3_54.txt | AC | 1 ms | 256 KB |
subtask3_55.txt | AC | 1 ms | 256 KB |
subtask3_56.txt | AC | 1 ms | 256 KB |
subtask3_57.txt | AC | 1 ms | 256 KB |
subtask3_58.txt | AC | 1 ms | 256 KB |
subtask3_59.txt | AC | 1 ms | 256 KB |
subtask3_60.txt | AC | 1 ms | 256 KB |
subtask3_61.txt | AC | 1 ms | 256 KB |
subtask3_62.txt | AC | 1 ms | 256 KB |
subtask3_63.txt | AC | 1 ms | 256 KB |
subtask3_64.txt | AC | 1 ms | 256 KB |
subtask3_65.txt | AC | 1 ms | 256 KB |