Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <stdio.h>
#include <queue>
int arr[201][201],chk[201];
std::queue<int> q;
int main(void) {
int i, j, v, n, cnt=0;
scanf("%d %d",&v,&n);
for(i=0;i<n;i++) {
int a,b;
scanf("%d %d",&a,&b);
arr[a][b]=1,arr[b][a]=-1;
}
while(cnt!=v){
for(i=1;i<=v;i++) {
if(!chk[i]) {
bool flag=0;
for(j=1;j<=v;j++)
if(arr[i][j]==-1) {
flag=1;
break;
}
if(!flag) break;
}
}
if(i>v) {
printf("-1");
return 0;
}
q.push(i);
for(int a=1;a<=v;a++) arr[a][i]=arr[i][a]=0;
chk[i]=1;
cnt++;
}
while(!q.empty()) {
printf("%d\n",q.front()); q.pop();
}
}
#include <stdio.h>
#include <queue>
#define MAX 30
#define INF 31415926
using namespace std;
queue<int> Q;
int dist[27],map[27][27], prt[27];
int w,tmp;
void print(int k){
if(prt[k]!=-1) print(prt[k]);
printf("%c\n", k+'A');
}
int main(){
int N, M; //N: node, M:edge
char from, to, start, end;
scanf("%d %d", &N, &M);
for(int i=0;i<N; i++) prt[i]=-1; //prt 초기화
for(int i=0;i<M;i++){
scanf(" %c %c %d", &from, &to, &w);
map[from-'A'][to-'A']=map[to-'A'][from-'A']=w;
}
scanf(" %c %c", &from, &to);
start=from-'A';
end=to-'A';
for(int i=0;i<N;i++) dist[i]=INF;
dist[start]=0;
//BFS
Q.push(start);
while(!Q.empty()){
tmp=Q.front();
Q.pop();
for(int i=0; i<N; i++){
if(map[tmp][i]&&dist[i]>dist[tmp]+map[tmp][i]){
dist[i]=dist[tmp]+map[tmp][i];
prt[i]=tmp;
Q.push(i);
}
}
}
if(dist[end]==INF){
printf("-1");
}
else {
printf("%d\n",dist[end]);
print(end);
}
return 0;
}
#include <stdio.h>
#include <queue>
int arr[1001][1001], sx, sy, fx, fy, tx, ty, nx, ny, n;
int dx[8]={2,-2,2,-2,1,-1,1,-1};
int dy[8]={1,1,-1,-1,2,2,-2,-2};
using namespace std;
queue<int> Qx, Qy;
int main(){
scanf("%d", &n);
scanf("%d %d", &sx, &sy);
scanf("%d %d", &fx, &fy);
arr[sx][sy]=1;
Qx.push(sx); Qy.push(sy);
while(!Qx.empty() && !Qy.empty()){
nx=Qx.front(); Qx.pop();
ny=Qy.front(); Qy.pop();
if(nx==fx && ny==fy) break;
for(int i=0; i<8; i++) {
tx=nx+dx[i]; ty=ny+dy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=n && arr[tx][ty]==0) {
Qx.push(tx); Qy.push(ty);
arr[tx][ty]=arr[nx][ny]+1;
}
}
}
printf("%d", arr[fx][fy]-1);
}
#include <stdio.h>
#include <queue>
using namespace std;
int map[111][111], n, m;
queue<int> qr, qc;
int count(int r, int c) {
return map[r-1][c] + map[r+1][c] + map[r][c-1] + map[r][c+1];
}
main() {
int i, j;
int tr, tc, flag = 0;
int res = 0;
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++) {
scanf("%d", &map[i][j]);
map[i][j] = !map[i][j];
}
while(1) {
flag = 0;
res++;
for(i = 2; i < n; i++)
for(j = 2; j < m; j++)
if ( map[i][j] == 0 && count(i, j) >= 2 ) {
flag = 1;
qr.push(i); qc.push(j);
}
if ( flag == 1 ) {
while( !qr.empty() ) {
tr = qr.front(); tc = qc.front();
map[tr][tc] = 1;
qr.pop(); qc.pop();
}
}
else {
printf("%d", res - 1);
return 0;
}
}
}
include <stdio.h>
int cheese[110][110];
int chk[110][110];
int cnt[110];
int r, c, num;
void air(int i,int j){
if(i>=1 && i<=r && j>=1 && j<=c){
if(!chk[i-1][j] && !cheese[i-1][j]) { chk[i-1][j]=-1; air(i-1,j); }
if(!chk[i][j-1] && !cheese[i][j-1]) { chk[i][j-1]=-1; air(i,j-1); }
if(!chk[i][j+1] && !cheese[i][j+1]) { chk[i][j+1]=-1; air(i,j+1); }
if(!chk[i+1][j] && !cheese[i+1][j]) { chk[i+1][j]=-1; air(i+1,j); }
}
}
void melt(){
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
if(cheese[i][j]==1)
if(chk[i-1][j]==-1||chk[i+1][j]==-1||chk[i][j-1]==-1||chk[i][j+1]==-1){
cheese[i][j]=0;
num--;
}
}
int main(void){
int cnt[110], t=0;
scanf("%d %d",&r,&c);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++){
scanf("%d",&cheese[i][j]);
num+=cheese[i][j];
}
while(1){
cnt[++t]=num;
if(num==0) break;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
chk[i][j]=0;
chk[1][1]=-1;
air(1,1);
melt();
}
printf("%d\n%d",t-1,cnt[t-1]);
}
#include <stdio.h>
int arr[102][102];
int temp[102][102];
int n;
void dfs(int i,int j) {
temp[i][j]=0;
if(temp[i+1][j]) dfs(i+1,j);
if(temp[i-1][j]) dfs(i-1,j);
if(temp[i][j+1]) dfs(i,j+1);
if(temp[i][j-1]) dfs(i,j-1);
return;
}
int main(void) {
int sum=0;
int max=0;
int smax=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) {
scanf("%d", &arr[i][j]);
if(arr[i][j]>max) max=arr[i][j];
}
for(int k=0;k<=max;k++) {
sum=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) {
if(arr[i][j]<=k) temp[i][j]=0;
else temp[i][j]=arr[i][j]-k;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) {
if(temp[i][j]) {
dfs(i,j);
sum++;
}
}
if(smax<sum) smax=sum;
}
printf("%d",smax);
}
#include <stdio.h>
int arr[502][502];
int n;
void floyd() {
int i, j, k;
for (k = 0; k < n; ++k) {
for (i = 1; i <=n; ++i) {
for (j = 1; j <=n; ++j) {
arr[i][j] = arr[i][j] | (arr[i][k + 1] && arr[k + 1][j]);
}
}
}
}
int main(void) {
int m;
int cnt=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++) {
int a,b;
scanf("%d %d",&a,&b);
arr[a][b]=1;
}
floyd();
for(int i=1;i<=n;i++) {
int in=0,out=0;
for(int j=1;j<=n;j++) if(arr[j][i]==1) in++;
for(int j=1;j<=n;j++) if(arr[i][j]==1) out++;
if((in+out)==n-1) cnt++;
}
printf("%d",cnt);
}
#include <stdio.h>
#include <algorithm>
int in[27][27], vis[27][27], dangi=0, h_num[900], cnt;
void dfs(int x, int y) {
vis[x][y]=1; cnt++;
if (in[x][y-1] && !vis[x][y-1]) dfs(x,y-1);
if (in[x][y+1] && !vis[x][y+1]) dfs(x,y+1);
if (in[x-1][y] && !vis[x-1][y]) dfs(x-1,y);
if (in[x+1][y] && !vis[x+1][y]) dfs(x+1,y);
}
int main () {
int n;
scanf("%d",&n);
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
scanf("%1d", &in[i][j]);
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (in[i][j] && !vis[i][j]) {
cnt=0;
dfs(i,j);
h_num[dangi]=cnt; dangi++;
}
}
}
std::sort(h_num, h_num+dangi);
printf("%d",dangi);
for (int i=0; i<dangi; i++) printf("\n%d", h_num[i]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.