#2327642

Solution for 1144: Curling 2.0 by n_knuu

Source Code Status Test Cases
    Policy: public     Reviewed: 4    
00.41 sec    181016 KB    67 lines     1762 bytes    2017-05-20 05:37
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

int R, C;
inline bool in(int r, int c) { return 0 <= r and r < R and 0 <= c and c < C; }

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  while (true) {
    cin >> R >> C;
    if (R == 0 and C == 0) break;
    vector<vector<int>> board(R, vector<int>(C));
    int sr = 0, sc = 0;
    REP(i, R) REP(j, C) {
      cin >> board[i][j];
      if (board[i][j] == 2) sr = i, sc = j;
    }
    board[sr][sc] = 0;

    bool flag = false;
    queue<tuple<int, int, vector<vector<int>>, int>> que;
    que.emplace(sr, sc, board, 0);
    while (not que.empty()) {
      int r, c, cnt; vector<vector<int>> board; tie(r, c, board, cnt) = que.front(); que.pop();

      if (board[r][c] == 3) {
        cout << cnt << endl;
        flag = true;
        break;
      }
      if (cnt == 10) break;

      REP(i, 4) {
        int nr = r + dr[i], nc = c + dc[i];
        if (in(nr, nc) and board[nr][nc] != 1) {
          while (in(nr, nc) and board[nr][nc] == 0) nr += dr[i], nc += dc[i];
          if (in(nr, nc) and cnt < 10) {
            vector<vector<int>> next_board = board;
            if (next_board[nr][nc] == 1) next_board[nr][nc] = 0, nr -= dr[i], nc -= dc[i];
            que.emplace(nr, nc, next_board, cnt + 1);
          }
        }
      }
    }
    if (not flag) cout << -1 << endl;
  }


  return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 0/1 C++14 CPU: 00.41 sec Memory: 181016 KB Length: 1762 B 2017-05-20 05:37 2017-05-20 05:37
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Memory Limit Exceeded 00.41 sec 181016 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags