リンク

質問リンク

問題の説明

ロボット掃除機がある場合は、清掃領域の個数を計算するプログラムを作成してください.
ロボット掃除機があるところはNです×Mサイズの長方形として表示できます.×1サイズの正方形の格子に分けます.各格子は壁またはスペースです.掃除機は向きがあり、この方向は東、西、南、北の一つです.地図の各格は(r,c)と表すことができ、rは北から来た格の個数であり、cは西から来た格の個数である.
ロボット掃除機の動作原理は以下の通りです.

現在位置をクリアします.

現在位置で、現在の方向を基準にして、左側から隣接するセルを順にナビゲートします.
a.左の方向に清掃されていないスペースがあれば、その方向に回転して、1番から格子を進みます.
b.左に清掃スペースがない場合は、その方向に回転して2番に戻ります.
c.4つの方向が清掃されているか、壁が清掃されている場合は、見ている方向を1つ後退させ、2番に戻ります.
d.4つの方向はすべて清掃または壁であり、後ろの方向が壁であり、バックできない場合は、作業を停止する.

ロボット掃除機は掃除した部屋を掃除しなくなり、壁を通ることができません.

入力

第1行は、縦方向サイズNおよび横方向サイズMを与える.(3 ≤ N, M ≤ 50)
2行目は、ロボット掃除機が位置するセルの座標(r,c)と向きdを示す.すなわち,dは0時に北へ,1時に東へ,2時に南へ,3時に西へである.
3行目からN行目では,場所の状態は北から南へ順に,各行は西から東へ順次であった.スペースは0、壁は1です.地図の最初の行、最後の行、最初の列、最後の列のすべてのセルは壁です.
ロボット掃除機のある部屋の状態はいつも空いています.

しゅつりょく

ロボット掃除機は清掃する車両数を出力します.

I/O例

に答える

呼...本当に言ったように、これは体現です・・・壁と掃除された資料だけを表示する仕組みを発表しただけで、残りは実施をキャンセル!

正確な解釈?これは無意味なシミュレーション問題だ.
でも問題を理解するのに時間がかかりました
また,問題の実質的な方向は2つある.(これは本当に紛らわしい…)
掃除機の方向(d)、現在回転する方向(tempdir)
これに合わせるのに時間がかかりました
それもシミュレーションの練習にいい問題です!
でもどうしてパソコンがこんなに遅くなったの?

コード#コード#

package Sample;
import java.util.*;
class Point{
	int x, y;
	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}
public class Main {	
	static int[][] map; //맵
	static boolean[][] visited; //청소 여부
	static int[] dx = {-1, 0, 1, 0}; //북 동 남 서
	static int[] dy = {0, 1, 0, -1}; //북 동 남 서
	static Stack<Point> st = new Stack<>();
	public static int get_left(int now) {
		if(now == 0)
			return 3;
		else
			return now - 1;
	}
	public static int get_back(int now_dir) {
		if(now_dir == 0) return 2;
		else if(now_dir == 1) return 3;
		else if(now_dir == 2) return 0;
		else return 1;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		map = new int[N][M];
		visited = new boolean[N][M];
		int r = sc.nextInt();
		int c = sc.nextInt();
		int d = sc.nextInt();

		st.push(new Point(r, c));
		visited[r][c] = true; //clean
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++)
				map[i][j] = sc.nextInt();
		
		int ans = 1;
		int rotate_cnt = 0;
		while(true) {
			int tempdir = get_left(d);
			int nx = st.peek().x + dx[tempdir];
			int ny = st.peek().y + dy[tempdir];
			if(map[nx][ny] == 1 || visited[nx][ny]) { //벽이거나 청소했을 때
				rotate_cnt++;
				d = tempdir;
				if(rotate_cnt == 4) { //뭐가됐든 4번을 돌았으면 후진을 해야함
					int bx = st.peek().x + dx[get_back(d)];
					int by = st.peek().y + dy[get_back(d)];
					if(map[bx][by] == 1) 
					{
						break;
					}
					st.push(new Point(bx,by));
					rotate_cnt = 0;
				}
			}
			else {
				st.push(new Point(nx,ny));
				visited[nx][ny] = true;
				map[nx][ny] = ++ans;
				d = tempdir;
				rotate_cnt = 0;
			}
		}
		System.out.println(ans);

	}
}