番号のみ(Baek Jun)
2843 ワード
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int Max = 25;
int N;
int DirX[4] = { -1,0,1,0 };
int DirY[4] = { 0,-1,0,1 };
int iCnt = 0;
char vvContents[25][25];
int vvChk[Max][Max] = { 0, };
vector<int> vDanji;
bool cmp(int x, int y)
{
return x < y; //내림차순 반환입니다.
}
void BFS(int x, int y)
{
queue<pair<int, int>> qTemp;
qTemp.push(make_pair(x, y));
vvChk[x][y] = 1;
iCnt++;
while (!qTemp.empty())
{
int iX = qTemp.front().first;
int iY = qTemp.front().second;
qTemp.pop();
for (int i = 0; i < 4; i++)
{
int iNX = iX + DirX[i];
int iNY = iY + DirY[i];
if ((vvChk[iNX][iNY] == 0) && (iNX >= 0) && (iNX < N) && (iNY >= 0) && (iNY < N) && (vvContents[iNX][iNY] == '1'))
{
iCnt++;
vvChk[iNX][iNY] = 1;
qTemp.push(make_pair(iNX, iNY));
}
}
}
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
cin >> vvContents[i];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if ((vvChk[i][j] == 0) && (vvContents[i][j] == '1'))
{
BFS(i, j);
vDanji.push_back(iCnt);
iCnt = 0;
}
}
}
sort(vDanji.begin(), vDanji.end(), cmp);
cout << vDanji.size() << endl;
for (int i = 0; i < vDanji.size(); i++)
{
cout << vDanji[i] << endl;
}
return 0;
}
これを解くと太陽が下山した.従来のBFSと異なり,0と1配列におけるブレークポイント(1不連続)
切断された部分に二重砲口を作らなければならない.
切断された部分をゾーン別に処理するには、Vector vDanjiを宣言する必要があります.
白俊が解くときに並ぶ青さは面倒だ.
char vvContents[25][25];
for (int i = 0; i < N; i++)
cin >> vvContents[i];
このように宣言するには、Vcontents[i][j]='1'を作ることを忘れないでください.文字列で処理します.0なので、空いているところも処分されていたので、ずっとやっていました.
Reference
この問題について(番号のみ(Baek Jun)), 我々は、より多くの情報をここで見つけました https://velog.io/@imalive77/단지번호붙이기백준-udodsfz6テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol