Programers:部屋数-C++
15733 ワード
部屋の数
コード#コード#
[DFSプール]
#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
// 2차원 좌표로 이루어진 그래프에서 순환 검사 + 예외처리
map<pair<int,int>, vector<pair<int,int>>> m;
map<pair<int,int>, bool> vis;
map<pair<pair<int,int>, pair<int,int>>, bool> make;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int ans=0;
void DFS(int Y, int X){
vis[{Y,X}] = true;
for(int i=0;i<m[{Y,X}].size();i++){
int ny = m[{Y,X}][i].first;
int nx = m[{Y,X}][i].second;
bool check = false;
if(make[{{Y,X}, {ny,nx}}] or make[{{ny,nx}, {Y,X}}]) check = true;
/* 해당 정점에 대해 방문하였으면서 && 처음 만들어지는 간선이면! */
if(vis[{ny,nx}] and !check) ans++;
else if(vis[{ny,nx}]) continue;
/* 간선은 하나지만, 방향은 2개가 될 수 있기에 2방향 모두 넣어줘야함 */
make[{{Y,X}, {ny,nx}}] = true;
make[{{ny,nx}, {Y,X}}] = true;
DFS(ny, nx);
}
}
int solution(vector<int> arrows) {
int curX = 0;
int curY = 0;
for(int i=0;i<arrows.size();i++)
{
/* 교차 예외 처리를 위해 2번식 이동 */
for(int j=0;j<2;j++)
{
int nx = curX + dx[arrows[i]];
int ny = curY + dy[arrows[i]];
bool flag = false;
m[{curY, curX}].push_back({ny, nx});
curY = ny;
curX = nx;
}
}
DFS(0,0);
return ans;
}
[DFSプール]
#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
// 2차원 좌표로 이루어진 그래프에서 순환 검사 + 예외처리
map<pair<int,int>, vector<pair<int,int>>> m;
map<pair<int,int>, bool> vis;
map<pair<pair<int,int>, pair<int,int>>, bool> make;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int ans=0;
void DFS(int Y, int X){
vis[{Y,X}] = true;
for(int i=0;i<m[{Y,X}].size();i++){
int ny = m[{Y,X}][i].first;
int nx = m[{Y,X}][i].second;
bool check = false;
if(make[{{Y,X}, {ny,nx}}] or make[{{ny,nx}, {Y,X}}]) check = true;
/* 해당 정점에 대해 방문하였으면서 && 처음 만들어지는 간선이면! */
if(vis[{ny,nx}] and !check) ans++;
else if(vis[{ny,nx}]) continue;
/* 간선은 하나지만, 방향은 2개가 될 수 있기에 2방향 모두 넣어줘야함 */
make[{{Y,X}, {ny,nx}}] = true;
make[{{ny,nx}, {Y,X}}] = true;
DFS(ny, nx);
}
}
int solution(vector<int> arrows) {
int curX = 0;
int curY = 0;
for(int i=0;i<arrows.size();i++)
{
/* 교차 예외 처리를 위해 2번식 이동 */
for(int j=0;j<2;j++)
{
int nx = curX + dx[arrows[i]];
int ny = curY + dy[arrows[i]];
bool flag = false;
m[{curY, curX}].push_back({ny, nx});
curY = ny;
curX = nx;
}
}
DFS(0,0);
return ans;
}
모든 풀이
参照얍문
( https://yabmoons.tistory.com/606 ) 방을 만드는 조건
)이미 방문한 정점
다시 방문
(vis
)처음
(make
)교차
)정점
ではチェックできない2개의 방
が作成されます.중간 지점
정점
교차점을 검사
-->이동
は2번으로 나누어서 진행
でなければなりません.:
재귀
を通過するには時間がかかります(반복문
より速い)[反復回答]
https://yabmoons.tistory.com/606
Reference
この問題について(Programers:部屋数-C++), 我々は、より多くの情報をここで見つけました https://velog.io/@neity16/Programers-방의-개수-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol