夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

頭が柔らかくなってきた。

こんな問題の解法が思いつくなんて少し前の俺には考えられなかった(たぶん)

0558

チーズは必ず1つずつで、1〜NのN個必ずあることが保証されているのでSから1、1から2、2から3・・・N-1〜Nまでの最短距離を全て足せばよい。
自分ででもBFSはかけるようになってきたが、一応個々の最短距離を求めるコードは蟻本見てしまった。

#include <iostream>
#include <map>
#include <queue>
#define INF 10000000
using namespace std;
typedef pair<int, int> P;
int h, w, n;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int d[1000][1000];
string field[1000];
P pos[10];
int bfs(P s, P g) {
    queue<P> que;
    for (int i=0; i<h; i++)
        for (int j=0; j<w; j++) d[i][j]=INF;
    que.push(P(s.first, s.second));
    d[s.first][s.second]=0;
    while (!que.empty()) {
        P p = que.front(); que.pop();
        if (p.first==g.first&&p.second==g.second) break;
        for (int i=0; i<4; i++) {
            int nx=p.first+dx[i], ny=p.second+dy[i];
            if (0<=nx&&nx<h&&0<=ny&&ny<w&&field[nx][ny]!='X'&&d[nx][ny]==INF) {
                que.push(P(nx,ny));
                d[nx][ny]=d[p.first][p.second]+1;
            }
        }
    }
    return d[g.first][g.second];
}
int main() {
    scanf("%d%d%d",&h,&w,&n);
    for (int i=0; i<h; i++) {
        cin >> field[i];
        for (int j=0; j<w; j++) {
            if (field[i][j]>'0'&&field[i][j]<='9') {
                pos[field[i][j]-'0']=make_pair(i,j);
            } else if (field[i][j]=='S') {
                pos[0]=make_pair(i,j);
            }
        }
    }
    int res=0;
    for (int i=0; i<n; i++) {
        res+=bfs(pos[i], pos[i+1]);
    }
    printf("%d\n",res);
}

0541

DP+シュミレーション。
あるところを通るのが全部でN回あるとするとN回反転する、つまりそのおよそ半分は左に、半分は下に行くことになる。
であるからそれぞれのマス目に行く回数をDPで求め、それによって最後のマップの状態をだし普通にシュミレーションする。
DPといったら大げさかもしれないけどDP的な考え方。

#include <cstdio>
#include <cmath>
int field[1000][1000];
int dp[1000][1000];
int h, w, n;
// 0---南 1---東
int main() {
    while (scanf("%d%d%d",&h,&w,&n)) {
        if (!h&&!w&&!n) break;
        for (int i=0; i<h; i++) for (int j=0; j<w; j++)
            scanf("%d",&field[i][j]);
        dp[0][0]=n;
        for (int i=1; i<w; i++) {
            if (field[0][i-1]&&dp[0][i-1]%2) {
                dp[0][i]=floor(dp[0][i-1]/2)+1;
            } else {
                dp[0][i]=floor(dp[0][i-1]/2);
            }
        }
        for (int i=1; i<h; i++) for (int j=0; j<w; j++) {
            dp[i][j]=0;
            if (!field[i-1][j]&&dp[i-1][j]%2) {
                dp[i][j]+=floor(dp[i-1][j]/2)+1;
            } else {
                dp[i][j]+=floor(dp[i-1][j]/2);
            }
            if (j&&field[i][j-1]&&dp[i][j-1]%2) {
                dp[i][j]+=floor(dp[i][j-1]/2)+1;
            } else {
                dp[i][j]+=floor(dp[i][j-1]/2);
            }
        }
        for (int i=0; i<h; i++) for (int j=0; j<w; j++) {
            if (dp[i][j]%2==0) {
                field[i][j]^=1;
            }
            // printf("%d%c",dp[i][j],j==w-1?'\n':' ');
        }
        int nx=0, ny=0;
        while (nx<h&&ny<w) {
            if (field[nx][ny]) ny++;
            else nx++;
        }
        printf("%d %d\n",nx+1,ny+1);
    }
}

今日はここらへんで。