Last active
June 14, 2018 02:58
-
-
Save jwon0615/77a830be9eb917b5866335fdcded9641 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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