Submission #105716

#	Time	Username	Problem	Language	Result	Execution time	Memory
105716		Pro_ktmr	Sandwich (JOI16_sandwich)	C++14	100 / 100	2070 ms	15496 KiB

sandwich

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()

int H,W;
string S[400];
int state[400][400]; //0:初期、1:計算中、2:計算終了
/*
 3
1 2
 0
*/
int dfs(int y, int x, int d){
	if(x < 0 || x >= W || y < 0 || y >= H) return 0;
	if(state[y][x] == 1) return INT_MAX;
	if(state[y][x] == 2) return 0;
	state[y][x] = 1;
	int ans = 1;
	if(S[y][x] == 'N'){
		if(d == 0 || d == 1){
			int tmp = dfs(y, x+1, 1);
			if(tmp == INT_MAX) return INT_MAX;
			ans += tmp;
			tmp = dfs(y-1, x, 0);
			if(tmp == INT_MAX) return INT_MAX;
			ans += tmp;
		}
		else{
			int tmp = dfs(y, x-1, 2);
			if(tmp == INT_MAX) return INT_MAX;
			ans += tmp;
			tmp = dfs(y+1, x, 3);
			if(tmp == INT_MAX) return INT_MAX;
			ans += tmp;
		}
	}
	if(S[y][x] == 'Z'){
		if(d == 0 || d == 2){
			int tmp = dfs(y, x-1, 2);
			if(tmp == INT_MAX) return INT_MAX;
			ans += tmp;
			tmp = dfs(y-1, x, 0);
			if(tmp == INT_MAX) return INT_MAX;
			ans += tmp;
		}
		else{
			int tmp = dfs(y, x+1, 1);
			if(tmp == INT_MAX) return INT_MAX;
			ans += tmp;
			tmp = dfs(y+1, x, 3);
			if(tmp == INT_MAX) return INT_MAX;
			ans += tmp;
		}
	}
	state[y][x] = 2;
	return ans;
}

int ans[400][400];
int main(){
	cin >> H >> W;
	for(int i=0; i<H; i++) cin >> S[i];

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			ans[i][j] = INT_MAX;
		}
	}
	
	//右から入る
	for(int i=0; i<H; i++){
		for(int k=0; k<H; k++){
			for(int l=0; l<W; l++){
				state[k][l] = 0;
			}
		}
		int tmp = 0;
		for(int j=0; j<W; j++){
			int tmp2 = dfs(i, j, 2);
			if(tmp2 == INT_MAX || tmp == INT_MAX) tmp = INT_MAX;
			else tmp += tmp2;
			ans[i][j] = min(ans[i][j], tmp);
		}
	}

	//左から入る
	for(int i=0; i<H; i++){
		for(int k=0; k<H; k++){
			for(int l=0; l<W; l++){
				state[k][l] = 0;
			}
		}
		int tmp = 0;
		for(int j=W-1; j>=0; j--){
			int tmp2 = dfs(i, j, 1);
			if(tmp2 == INT_MAX || tmp == INT_MAX) tmp = INT_MAX;
			else tmp += tmp2;
			ans[i][j] = min(ans[i][j], tmp);
		}
	}

	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			if(j != 0) cout << " ";
			if(ans[i][j] == INT_MAX) cout << -1;
			else cout << ans[i][j]*2;
		}
		cout << endl;
	}

	return 0;
}

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65