したらばTOP ■掲示板に戻る■ 全部 1-100 最新50 | メール | |

管理人の独り言（プログラミング関連）

1521： ◆adhRKFl5jU：2009/03/01(日) 18:27:55
jid14
問題番号 6
点数 100
-----
/*
TASK: Sheet
LANG: C++
NAME: Kazuhiro Hosaka JPN13
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <bitset>
#include <complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i=a; i!=b; ++i) cout << *i << " "; cout << endl; }
template<class T> void pvp(T a, T b) { for (T i=a; i!=b; ++i) cout << "(" << i->first << ", " << i->second << ") "; cout << endl; }

const int INF = 1001001001;

int N;
int H,W;
int A[110][110];
int minx[1010],miny[1010],maxx[1010],maxy[1010];
int prior[1010][1010],vis[1010];
int ord[1010],ordlen;

void dfs(int u) {
vis[u] = 1;
for (int v=0; v<N; ++v) if (!vis[v] && prior[u][v]) dfs(v);
ord[ordlen++] = u;
}

int main() {
//freopen("sheet.in", "r", stdin);

int u,v;
int x,y;

scanf("%i", &N);
scanf("%i%i", &W, &H);

for (u=0; u<N; ++u) {
minx[u] = miny[u] = INF;
maxx[u] = maxy[u] = -INF;
}

for (x=0; x<H; ++x) for (y=0; y<W; ++y) {
scanf("%i", &u);
A[x][y] = --u;
if (u >= 0) {
minx[u] = min(minx[u], x); miny[u] = min(miny[u], y);
maxx[u] = max(maxx[u], x); maxy[u] = max(maxy[u], y);
}
}

for (u=0; u<N; ++u) {
if (minx[u] > maxx[u]) { // invisible paper
for (v=0; v<N; ++v) {
prior[v][u] = 1;
}
} else {
for (x=minx[u]; x<=maxx[u]; ++x) for (y=miny[u]; y<=maxy[u]; ++y) {
if (A[x][y] >= 0) prior[A[x][y]][u] = 1;
}
}
}

for (u=0; u<N; ++u) if (!vis[u]) dfs(u);
for (u=0; u<N; ++u) {
if (u) putchar(' ');
printf("%i", ord[u] + 1);
}
puts("");


return 0;
}
新着レスの表示

名前： E-mail（省略可）：

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）
掲示板管理者へ連絡 無料レンタル掲示板