Codeforces 659F Polycarp and Hay【BFS】
6908 ワード
毒があって、前回の选抜试合(泣いて)1つのごみbfsが书き间违ってから、毎回bfsを书くたびにWAが何発かかかります...まあ、実は今回だけ...白さんの言うとおりです.やはりコード能力が足りません..とても足りません...
タイトルリンク:
http://codeforces.com/contest/659/problem/F
タイトル:
n*mの格子は、各格子に1つの数があり、この数以下の任意の数を格子から減算しなければならない.与えられた数字k、要求:残りの格子数とkです. すべてのゼロでない格子の数字は同じであるべきである. 少なくとも1つの格子の数字は変更されていません. ゼロ以外の数字を含む格子は連通するべきである.
分析:
kで除去され、n*m未満の格子を除去できる各数字を列挙し、bfsは格子を探して、結合ブロックが条件を満たすかどうかを見る.これまで最適化は行われておらず、TLE on 95.後で別の配列を設けて、すでに列挙した数を記録して、前と同じ数に出会って、この数が満足していないことを説明して、直接スキップすることができて、考慮しなくてもいいです.
コード:
タイトルリンク:
http://codeforces.com/contest/659/problem/F
タイトル:
n*mの格子は、各格子に1つの数があり、この数以下の任意の数を格子から減算しなければならない.与えられた数字k、要求:
分析:
kで除去され、n*m未満の格子を除去できる各数字を列挙し、bfsは格子を探して、結合ブロックが条件を満たすかどうかを見る.これまで最適化は行われておらず、TLE on 95.後で別の配列を設けて、すでに列挙した数を記録して、前と同じ数に出会って、この数が満足していないことを説明して、直接スキップすることができて、考慮しなくてもいいです.
コード:
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 1e3 + 5;
#define x first
#define y second
#define sa(a) scanf("%d", &a)
#define sal(a) scanf("%I64d", &a)
typedef pair<int, int> pii;
int vis[maxn][maxn];
int a[maxn][maxn], c[maxn][maxn];
int m, n;
long long k;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool bfs(pii pa, int res)
{
queue<pii>q;
memset(vis, false, sizeof(vis));
vis[pa.x][pa.y] = true;
q.push(pa);
int cnt = 1;
while(!q.empty()){
pii t = q.front();q.pop();
int x = t.x, y = t.y;
if(cnt == res) return true;
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny]){
if(a[nx][ny] < a[pa.x][pa.y]) continue;
if(a[nx][ny] == a[pa.x][pa.y]) c[nx][ny] = 1;
vis[nx][ny] = true;
cnt ++;
q.push(pii(nx, ny));
if(cnt == res) return true;
}
}
}
return false;
}
int solve()
{
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(c[i][j]) continue;
long long cnt = k/ a[i][j];
if(k % a[i][j] == 0 && cnt <= m * n){
if(bfs(pii(i, j), cnt)) return a[i][j];
}
}
}
return -1;
}
int main (void)
{
sa(n),sa(m),sal(k);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
sa(a[i][j]);
}
}
int ans = solve();
if(ans == -1) return printf("NO
"), 0;
printf("YES
");
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(vis[i][j]) printf("%d%c", ans, j == m - 1? '
':' ');
else printf("0%c", j == m - 1?'
':' ');
}
}
return 0;
}