fork download
copy 
  1. #include<iostream>
  2. #include<queue>
  3.  
  4. #define endl "\n"
  5. #define MAX 2000
  6. using namespace std;
  7. queue<pair<pair<int, int>, int> > Q;
  8. int S;
  9. bool Visit[MAX][MAX];
  10.  
  11. void Input()
  12. {
  13.     cin >> S;
  14. }
  15.  
  16. int BFS()
  17. {
  18.  
  19.     Q.push(make_pair(make_pair(1, 0), 0));
  20.     Visit[1][0] = true;    // 화면, 클립보드
  21.  
  22.     while (Q.empty() == 0)
  23.     {
  24.         int Dis = Q.front().first.first;
  25.         int Clip = Q.front().first.second;
  26.         int Time = Q.front().second;
  27.         Q.pop();
  28.  
  29.         if (Dis == S) return Time;
  30.  
  31.         if (Dis > 0 && Dis < MAX)
  32.         {
  33.             //1번 & 3번 조건
  34.             if (Visit[Dis][Dis] == false)
  35.             {
  36.                 Visit[Dis][Dis] = true;
  37.                 Q.push(make_pair(make_pair(Dis, Dis), Time + 1));
  38.             }
  39.  
  40.             if (Visit[Dis - 1][Clip] == false)
  41.             {
  42.                 Visit[Dis - 1][Clip] = true;
  43.                 Q.push(make_pair(make_pair(Dis - 1, Clip), Time + 1));
  44.             }
  45.         }
  46.  
  47.         if (Clip > 0 && Dis + Clip < MAX)
  48.         {
  49.             if (Visit[Dis + Clip][Clip] == false)
  50.             {
  51.                 Visit[Dis + Clip][Clip] = true;
  52.                 Q.push(make_pair(make_pair(Dis + Clip, Clip), Time + 1));
  53.             }
  54.         }
  55.     }
  56. }
  57.  
  58.  
  59. void Solution()
  60. {
  61.     int R = BFS();
  62.     cout << R << endl;
  63. }
  64.  
  65. void Solve()
  66. {
  67.     Input();
  68.     Solution();
  69. }
  70.  
  71. int main(void)
  72. {
  73.     ios::sync_with_stdio(false);
  74.     cin.tie(NULL);
  75.     cout.tie(NULL);
  76.  
  77.     //freopen("Input.txt", "r", stdin);
  78.     Solve();
  79.  
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 7456KB
comments (?)
stdin
copy 
997
stdout
copy 
23
https://ideone.com/igZsAQ
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!