Submission #4065174

---

Source Code Expand

#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

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

int N, M, K;
int si, sj;
char F[811][811];
int W[811][811];
int D[811][811];

bool in(int y, int x) {
    return 0 <= y && y < N && 0 <= x && x < M;
}

void MAIN() {
    scanf("%d%d%d", &N, &M, &K);
    REP (i, N) scanf("%s", F[i]);

    REP (i, N) REP (j, M) if (F[i][j] == 'S') {
	si = i;
	sj = j;
    }
    memset(W, 0x3f, sizeof W);
    const int INF = W[0][0];

    stack<pair<int, int> > cur, nxt;
    W[si][sj] = 0;
    cur.emplace(si, sj);
    while (1) {
	if (cur.empty()) swap(cur, nxt);
	if (cur.empty()) break;

	int y = cur.top().first;
	int x = cur.top().second;
	cur.pop();
	REP (d, 4) {
	    int yy = y + dy[d];
	    int xx = x + dx[d];
	    if (in(yy, xx) && W[yy][xx] == INF) {
		if (F[yy][xx] == '.') {
		    W[yy][xx] = W[y][x];
		    cur.emplace(yy, xx);
		} else {
		    W[yy][xx] = W[y][x] + 1;
		    nxt.emplace(yy, xx);
		}
	    }
	}
    }

    memset(D, 0x3f, sizeof D);
    D[si][sj] = 0;
    cur.emplace(si, sj);
    stack<pair<int, int> > nnxt;
    nnxt.emplace(si, sj);

    int ans = 1;
    while (1) {
	bool ok = false;
	REP (i, K) {
	    if (cur.empty()) break;
	    while (!cur.empty()) {
		int y = cur.top().first;
		int x = cur.top().second;
		cur.pop();
		REP (d, 4) {
		    int yy = y + dy[d];
		    int xx = x + dx[d];
		    if (in(yy, xx) && D[yy][xx] == INF && W[yy][xx] <= (ans - 1) * K) {
			D[yy][xx] = D[y][x] + 1;
			nxt.emplace(yy, xx);
			nnxt.emplace(yy, xx);
			if (yy == 0 || yy == N-1 || xx == 0 || xx == M-1) ok = true;
		    }
		}
	    }
	    swap(cur, nxt);
	}

	while (!cur.empty()) cur.pop();
	swap(cur, nnxt);

	if (ok) {
	    break;
	} else {
	    ans++;
	}
    }

    printf("%d\n", ans);
}


int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void MAIN()’:
./Main.cpp:38:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &M, &K);
                                ^
./Main.cpp:39:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     REP (i, N) scanf("%s", F[i]);
                                 ^

Judge Result