题解 - Vijos

1

酷暑一夏1 LV 9 @ 2017-09-03 14:21:53

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while ( ch < '0' || ch > '9' )
    {
        if ( ch == '-' )
            f = -1;
        ch = getchar();
    }
    while ( ch >= '0' && ch <= '9' )
    {
        x = x * 10 + ch - '0'; ch = getchar();
    }
    return(x * f);
}


typedef pair<int, int> PII;
const int   N = 1000 + 5;
int     n, k, mp[N][N], color[N][N];
queue<PII>  q;
const int   dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
void dfs( int x, int y, int t )
{
    for ( int i = 0; i < 8; i++ )
    {
        int nx = x + dx[i], ny = y + dy[i];
        if ( nx >= 0 && nx <= n && ny >= 0 && ny <= n && color[nx][ny] == 0 )
        {
            if ( mp[nx][ny] == mp[x][y] )
            {
                color[nx][ny] = t;
                dfs( nx, ny, t );
            } else {
                color[nx][ny] = t + 1;
                q.push( make_pair( nx, ny ) );
            }
        }
    }
}


void bfs()
{
    PII s = make_pair( 0, 0 );
    q.push( s );
    color[0][0] = 1;
    while ( !q.empty() )
    {
        PII p = q.front();
        q.pop();
        dfs( p.first, p.second, color[p.first][p.second] );
    }
}


int main()
{
    scanf( "%d%d", &n, &k );
    getchar();
    for ( int i = 1; i <= n; i++ )
    {
        for ( int j = 1; j <= n; j++ )
        {
            char ch; scanf( "%c", &ch );
            mp[i][j] = ch - '0';
        }
        getchar();
    }
    n++;
    bfs();
    for ( int i = 1; i <= k; i++ )
    {
        int x, y; scanf( "%d%d", &x, &y );
        printf( "%d%c", (color[x][y] - 1) / 2, i == k ? '\n' : ' ' );
    }
    return(0);
}

上几层楼的代码的美化版本

0

Uhen LV 7 @ 2017-03-21 16:29:33

#   状态  耗时  内存占用
#1   Accepted   2ms 1.188MiB
#2   Accepted   2ms 1.195MiB
#3   Accepted   2ms 1.574MiB
#4   Accepted   2ms 1.574MiB
#5   Accepted   53ms    6.336MiB
#6   Accepted   69ms    7.078MiB
#7   Accepted   80ms    6.953MiB
#8   Accepted   80ms    7.195MiB
#9   Accepted   68ms    6.684MiB
#10  Accepted   67ms    6.066MiB

具体的解释戳这里，
代码：

#include <bits/stdc++.h>
const int color_cnt = 200000;
int n, k, ans[color_cnt], map[1000][1000];
char ns[1007][1007];
int money;

int color;
const int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};

inline
void fill(int x, int y) {
    map[x][y] = color;
    for (int i = 0; i < 8; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n)
            continue;
        if (map[nx][ny]) {
            money = (!ns[x][y]) && ns[nx][ny];
            if (ans[map[nx][ny]] + money < ans[color]) {
                ans[color] = ans[map[nx][ny]] + money;
            }
            continue;
        }
        if (ns[nx][ny] != ns[x][y]) {
            continue;
        }
        fill(nx, ny);
    }
}

inline
void flood_fill() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (map[i][j]) continue;
            ++color;
            fill(i, j);
        }
    }
}

inline
void search(int x, int y, int init = 0) {
    if (map[x][y]) return;
    ++color;
    ans[color] = init;
    fill(x, y);
}

inline
void init() {
    memset(ans, 0x7f, sizeof(ans));
    for (int i = 0; i < n; ++i) {
        search(i, 0);
        search(0, i);
        search(i, n - 1);
        search(n - 1, i);
    }
}

inline
void bfs()
{
    init();
    flood_fill();
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%s", ns[i]);
        for (int j = 0; j < n; ++j) {
            ns[i][j] -= '0';
        }
    }

    bfs();

    for (int i = 0, a, b; i < k; ++i) {
        scanf("%d%d", &a, &b);
        --a, --b;
        printf("%d ", ans[map[a][b]]);
    }

    return 0;
}

0

WeiSama LV 8 @ 2017-01-24 15:13:21

dfs(本层染色)+bfs（跳到下层染色）陆->水->陆->水->陆，ans = (color[x][y] - 1)/2
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

inline int read() {
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}

typedef pair<int, int> PII;
const int N = 1000 + 5;

int n, k, mp[N][N], color[N][N];
queue<PII> q;
const int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };

void dfs(int x, int y, int t) {
for (int i = 0; i < 8; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx <= n && ny >= 0 && ny <= n && color[nx][ny] == 0) {
if (mp[nx][ny] == mp[x][y]) {
color[nx][ny] = t;
dfs(nx, ny, t);
} else {
color[nx][ny] = t + 1;
q.push(make_pair(nx, ny));
}
}
}
}

void bfs() {
PII s = make_pair(0, 0);
q.push(s);
color[0][0] = 1;
while (!q.empty()) {
PII p = q.front();
q.pop();
dfs(p.first, p.second, color[p.first][p.second]);
}
}

int main() {
scanf("%d%d", &n, &k);
getchar();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
char ch; scanf("%c", &ch);
mp[i][j] = ch - '0';
}
getchar();
}
n++;
bfs();
for (int i = 1; i <= k; i++) {
int x, y; scanf("%d%d", &x, &y);
printf("%d%c", (color[x][y] - 1) / 2, i == k ? '\n' : ' ');
}
return 0;
}

0

dkfleet LV 10 @ 2015-01-17 15:05:18

STL也不算慢嘛.....
裸的SPFA妥妥的TLE....

#include <cstdio>
#include <iostream>
#include <fstream>

#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>

#include <vector>
#include <queue>

typedef long long int ll;
typedef double db;
typedef unsigned short ush;

using namespace std;
const int INF=(1<<28)-1;

struct edge
{
int in;
char v;
edge*nxt;
}pool[10000000];
edge*et=pool;
edge*eds[1005000];
inline void addedge(int i,int j,char v)
{ et->in=j; et->v=v; et->nxt=eds[i]; eds[i]=et++; }
#define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)

int n,m;

int st;

char M[1050][1050];
int d[1005000];
typedef pair<int,int> pl;
priority_queue<pl,vector<pl>,greater_equal<pl> > q;
int qh,qt;

int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",M[i]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
M[i][j]-='0';

st=n*n;

int b=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int curp=b+j;

if(i==0 || j==0 || i==n-1 || j==n-1)
{ addedge(st,curp,M[i][j]); }

bool adj=(j+1<n);
bool dcj=(j>=1);
bool adi=(i+1<n);
bool dci=(i>=1);

if(adj) addedge(curp,curp+1,M[i][j]^M[i][j+1]);
if(dcj) addedge(curp,curp-1,M[i][j]^M[i][j-1]);
if(adi) addedge(curp,curp+n,M[i][j]^M[i+1][j]);
if(dci) addedge(curp,curp-n,M[i][j]^M[i-1][j]);

if(adi && adj) addedge(curp,curp+n+1,M[i][j]^M[i+1][j+1]);
if(dci && dcj) addedge(curp,curp-n-1,M[i][j]^M[i-1][j-1]);
if(adi && dcj) addedge(curp,curp+n-1,M[i][j]^M[i+1][j-1]);
if(dci && adj) addedge(curp,curp-n+1,M[i][j]^M[i-1][j+1]);
}
b+=n;
}

for(int i=0;i<=n*n;i++)
d[i]=INF;

q.push(pl(d[st]=0,st));
while(!q.empty())
{
int cur=q.top().second;
q.pop();

FOREACH_EDGE(i,cur)
if(i->v+d[cur]<d[i->in])
{
d[i->in]=d[cur]+i->v;
q.push(pl(d[i->in],i->in));
}
}

for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d ",d[a*n-n+b-1]>>1);
}
printf("\n");

return 0;
}

0

jixinye139 LV 10 @ 2014-12-12 18:11:59

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 7668 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 7672 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 7680 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 7684 KiB, score = 10
测试数据 #4: Accepted, time = 156 ms, mem = 7964 KiB, score = 10
测试数据 #5: Accepted, time = 187 ms, mem = 8136 KiB, score = 10
测试数据 #6: Accepted, time = 265 ms, mem = 7948 KiB, score = 10
测试数据 #7: Accepted, time = 296 ms, mem = 8024 KiB, score = 10
测试数据 #8: Accepted, time = 296 ms, mem = 7992 KiB, score = 10
测试数据 #9: Accepted, time = 234 ms, mem = 7780 KiB, score = 10
Accepted, time = 1464 ms, mem = 8136 KiB, score = 100
最长的时候写了200+的代码还超时了，后来发现其实没有那么复杂，只要一开始染色一下，之后就处于一种离线的状态了，对于染色，有人说要并查集，个人感觉完全没必要，dfs就已经够了。
Ps：我最后的代码只有50+左右，大家不要把题目想复杂了

0

jixinye139 LV 10 @ 2014-12-10 19:46:40

求数据阿，实在不清楚自己哪里错了

0

qaz LV 9 @ 2013-11-03 10:06:09

评测状态 Runtime Error
题目 P1468 渡河
递交时间 2013-11-03 10:03:48
代码语言 Pascal
评测机上海红茶馆
消耗时间 2355 ms
消耗内存 72492 KiB
评测时间 2013-11-03 10:03:49
评测结果
编译成功

foo.pas(126,24) Warning: Variable "m" does not seem to be initialized
测试数据 #0: Accepted, time = 31 ms, mem = 71444 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 71440 KiB, score = 10
测试数据 #2: Accepted, time = 46 ms, mem = 71444 KiB, score = 10
测试数据 #3: Accepted, time = 46 ms, mem = 71440 KiB, score = 10
测试数据 #4: RuntimeError, time = 343 ms, mem = 72488 KiB, score = 0
测试数据 #5: RuntimeError, time = 359 ms, mem = 72492 KiB, score = 0
测试数据 #6: RuntimeError, time = 375 ms, mem = 72488 KiB, score = 0
测试数据 #7: RuntimeError, time = 375 ms, mem = 72488 KiB, score = 0
测试数据 #8: RuntimeError, time = 421 ms, mem = 72488 KiB, score = 0
测试数据 #9: RuntimeError, time = 328 ms, mem = 72492 KiB, score = 0
RuntimeError, time = 2355 ms, mem = 72492 KiB, score = 40
代码
const
ma=2000100;
dx:array[1..8]of longint=(1,1,1,0,0,-1,-1,-1);
dy:array[1..8]of longint=(-1,0,1,-1,1,-1,0,1);
var
s2:ansistring;
g1,g2,s1,m,i,n,t,w,xx,yy,o,x,y,k,j,p:longint;
a:array[0..1010,0..1010]of longint;
b,bb:array[0..1010,0..1010]of boolean;
pd:array[0..ma+100]of boolean;
d:array[0..ma+100,1..2]of longint;
dd,fa,l,dis,q,h:array[0..ma+100]of longint;
procedure make(i,x,y:longint);
begin
h[i]:=y;
q[i]:=l[x];
l[x]:=i
end;
function gf(x:longint):longint;
begin
if x=fa[x] then
exit(x);
gf:=gf(fa[x]);
fa[x]:=gf;
end;
begin

readln(n,k);
fillchar(a,sizeof(a),0);
fillchar(fa,sizeof(fa),0);
for i:=2 to n+1 do
begin
readln(s2);
for j:=1 to n do
begin
xx:=ord(s2[j])-48;
a[i,j+1]:=xx;
fa[(i-1)*(n+2)+j+1]:=(i-1)*(n+2)+j+1;
end;
end;
n:=n+2;

{for i:=1 to n do
begin
for j:=1 to n do
write(' ',gf((i-1)*n+j));
writeln;
end; }

fillchar(b,sizeof(b),true);
for i:=1 to n do
for j:=1 to n do
if b[i,j] then
begin
b[i,j]:=false;
// xx:=(i-1)*n+j;
t:=1;
w:=1;
d[t,1]:=i;
d[w,2]:=j;
repeat
x:=d[t,1];
y:=d[t,2];
for o:=1 to 8 do
begin
xx:=x+dx[o];
yy:=y+dy[o];
if (xx>=1)and(yy>=1)and(xx<=n)and(yy<=n)and(a[xx,yy]=a[x,y]) then
begin
if gf((xx-1)*n+yy)<>gf((x-1)*n+y) then
fa[(xx-1)*n+yy]:=gf((x-1)*n+y);
if(b[xx,yy]) then
begin
w:=(w+1)mod ma;
d[w,1]:=xx;
d[w,2]:=yy;
b[xx,yy]:=false;
end;
end;
end;
t:=(t+1)mod ma;
until t=w+1;
end;

{for i:=1 to n do
begin
for j:=1 to n do
write(' ',gf((i-1)*n+j));
writeln;
end; }

fillchar(b,sizeof(b),true);
fillchar(bb,sizeof(bb),false);
for i:=1 to n do
for j:=1 to n do
if b[i,j] then
begin
b[i,j]:=false;
// xx:=(i-1)*n+j;
t:=1;
w:=1;
d[t,1]:=i;
d[w,2]:=j;
repeat
x:=d[t,1];
y:=d[t,2];
for o:=1 to 8 do
begin
xx:=x+dx[o];
yy:=y+dy[o];
if (xx>=1)and(yy>=1)and(xx<=n)and(yy<=n)and(a[xx,yy]=a[x,y])and(b[xx,yy]) then
begin
// if gf((xx-1)*n+yy)<>gf((x-1)*n+y)then
// fa[(xx-1)*n+yy]:=gf((x-1)*n+y);
w:=(w+1)mod ma;
d[w,1]:=xx;
d[w,2]:=yy;
b[xx,yy]:=false;
end;
if (xx>=1)and(yy>=1)and(xx<=n)and(yy<=n)and(a[xx,yy]<>a[x,y])and(not bb[gf((x-1)*n+y),gf((xx-1)*n+yy)])then
begin
bb[gf((x-1)*n+y),gf((xx-1)*n+yy)]:=true;
m:=m+1;
g1:=gf((x-1)*n+y);
g2:=gf((xx-1)*n+yy);
make(m,g1,g2);
m:=m+1;
make(m,g2,g1);
if b[xx,yy] then
begin
w:=(w+1)mod ma;
d[w,1]:=xx;
d[w,2]:=yy;
b[xx,yy]:=false;
end;
end;
end;
t:=(t+1)mod ma;
until t mod ma=(w+1)mod ma;
end;

for i:=1 to k do
begin
readln(x,y);
x:=x+1; y:=y+1;
p:=gf((x-1)*n+y);
fillchar(pd,sizeof(pd),true);
fillchar(dis,sizeof(dis),0);
dd[1]:=p;
t:=1;
w:=1;
repeat
x:=dd[t];
if dd[t]=0 then
begin
if i=1 then
write(dis[0] div 2) else
write(' ',dis[0] div 2);
break;
end;
s1:=l[dd[t]];
while s1<>0 do
begin
y:=h[s1];
if pd[y]then
begin
pd[y]:=false;
dis[y]:=dis[x]+1;
w:=(w+1)mod ma;
dd[w]:=y;
end;
s1:=q[s1];
end;
t:=(t+1)mod ma;
until t mod ma=(w+1)mod ma;
end;
writeln;

end.
为是么总是run time error 不可能超过数组限制啊

0

absi2011 LV 8 @ 2013-08-14 14:55:30

Orz各位的题解

0

ckl8520 LV 10 @ 2009-10-22 16:49:03

直接SPFA就可以了，当被修改的数值=当前数值时，

加到队首，而不是队尾

0

陈亮宇 LV 10 @ 2009-10-22 14:50:02

没了puppy 过不了啊！

p.s. 询问指向的不一定是陆地。。

第二个点好像就不是指向陆地的

0

尖端才子 LV 10 @ 2009-09-19 12:24:53

BFS+DFS的Flood fill……这是我的算法……

建立Open表和Close表……

0

LV 0 @ 2009-08-02 22:05:14

多次BFS floodfill

先找个最外层的陆地，开始8方向BFS，同时把接触到的水记录下来，然后对接触到的水8方向BFS，把接触到的陆地记录下来。。。这样循环往复。BFS只在同样的地形中进行，碰到不同的地形就记录到下一层中。

0

oimaster LV 10 @ 2009-06-19 21:15:02

一直没有注意到8连通是一层夹一层的……

FloodFill还有不少细节要注意……

0

pxoylngx LV 8 @ 2009-06-18 09:19:29

只能4个方向？

0

sedongji LV 3 @ 2008-11-04 18:21:19

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 103ms

├ 测试数据 06：答案正确... 150ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 181ms

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 212ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：827ms

0

dengyuans LV 8 @ 2008-11-03 16:59:45

大牛们能不能讲一下 flood fill是什么玩意儿?

0

j262492438 LV 3 @ 2008-10-30 22:21:22

我的 dfs 100+ uac啊

郁闷

0

cixiwxs LV 7 @ 2008-10-30 18:30:29

能不能给我测试数据

0

ferther LV 3 @ 2008-10-27 21:04:27

跪求：：：记忆化搜索可不可以啊！！！！

0

R.Aurora LV 3 @ 2008-10-23 22:18:19

编译通过...

├ 测试数据 01：内存溢出...

├ 测试数据 02：内存溢出...

├ 测试数据 03：内存溢出...

├ 测试数据 04：内存溢出...

├ 测试数据 05：内存溢出...

├ 测试数据 06：内存溢出...

├ 测试数据 07：内存溢出...

├ 测试数据 08：内存溢出...

├ 测试数据 09：内存溢出...

├ 测试数据 10：内存溢出...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：0 有效耗时：0ms

为什么我怎么改都是内存溢出？大牛们是怎么存储的？

题解

39 条题解

渡河

信息

状态

开发

支持

题解

39 条题解

渡河

信息

状态

开发

支持

还没有账户？

登录