Submission #1262103
Source Code Expand
# include <bits/stdc++.h> # define rep(i, n) for (int i = 0; i < (int)(n); i++) # define irep(i, n) for (int i = int(n) - 1; i >= 0; i--) # define FOR(i, m, n) for (int i = int(m); i < (int)(n); i++) using namespace std; int H, W; int nonzero = 0; vector<int> di = {0, 1}; vector<int> dj = {1, 0}; // namespace utils namespace utils{ template <typename T> void print(vector<vector<T>> mat) { rep (i, mat.size()) { rep (j, mat[0].size()) cout << mat[i][j] << ' '; cout << endl; } } template <typename T> void print(vector<T> v) { rep (i, v.size()) cout << v[i] << ' '; cout << endl; } // end namespace utils } bool restricted_dfs(vector<vector<char>> &A, int i, int j, int cnt) { // cout << cnt << "(" << nonzero << ")" << endl; if (H == i && W == j && cnt == nonzero) { return true; } rep (k, 2) { int next_i = i + di[k]; int next_j = j + dj[k]; if (next_i <= A.size()-1 && next_j <= A[0].size()-1 && \ next_i >= 0 && next_j >= 0 && A[next_i][next_j] == '#') { return restricted_dfs(A, next_i, next_j, ++cnt); // return じゃないとダメな理由 } } return false; } int main() { cin >> H >> W; vector<vector<char>> A(H); rep (i, H) { vector<char> row(W); rep (i, W) { cin >> row[i]; if (row[i] == '#') nonzero++; } A[i] = row; } // utils::print(A); H--; W--; if (restricted_dfs(A, 0, 0, 1)) cout << "Possible" << endl; else cout << "Impossible" << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Shik and Stone |
User | himkt |
Language | C++14 (GCC 5.4.1) |
Score | 200 |
Code Size | 1572 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0.txt, example1.txt, example2.txt |
All | 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, example0.txt, example1.txt, example2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000.txt | AC | 1 ms | 256 KB |
001.txt | AC | 1 ms | 256 KB |
002.txt | AC | 1 ms | 256 KB |
003.txt | AC | 1 ms | 256 KB |
004.txt | AC | 1 ms | 256 KB |
005.txt | AC | 1 ms | 256 KB |
006.txt | AC | 1 ms | 256 KB |
007.txt | AC | 1 ms | 256 KB |
008.txt | AC | 1 ms | 256 KB |
009.txt | AC | 1 ms | 256 KB |
010.txt | AC | 1 ms | 256 KB |
011.txt | AC | 1 ms | 256 KB |
012.txt | AC | 1 ms | 256 KB |
013.txt | AC | 1 ms | 256 KB |
014.txt | AC | 1 ms | 256 KB |
015.txt | AC | 1 ms | 256 KB |
016.txt | AC | 1 ms | 256 KB |
017.txt | AC | 1 ms | 256 KB |
018.txt | AC | 1 ms | 256 KB |
example0.txt | AC | 1 ms | 256 KB |
example1.txt | AC | 1 ms | 256 KB |
example2.txt | AC | 1 ms | 256 KB |