在无边的板上铺电线

import sys STEP = {"U": (0, 1), "D": (0, -1), "L": (-1, 0), "R": (1, 0)}  def main():    lines = sys.stdin.read().split("\n")    q = int(lines[0])    owner = {}   # (x, y) → 전선 번호. 튜플은 값이 같으면 같은 열쇠다    wires = {}   # 전선 번호 → 그 전선이 차지한 칸들    next_id = 1    out = []    for line in lines[1:1 + q]:        parts = line.split()        x, y = int(parts[1]), int(parts[2])        if parts[0] == "lay":            path = [(x, y)]            for ch in parts[3]:                dx, dy = STEP[ch]                x, y = x + dx, y + dy                path.append((x, y))            hit = next((cell for cell in path if cell in owner), None)  # 길 순서로 처음 막히는 칸            if hit is not None:                out.append(f"blocked {owner[hit]}")  # 아무 칸도 놓지 않는다                continue            mine = list(dict.fromkeys(path))  # 자기 길을 다시 지나는 칸은 한 번만            for cell in mine:                owner[cell] = next_id            wires[next_id] = mine            out.append(f"ok {len(mine)}")            next_id += 1        else:            if (x, y) in owner:                wire = owner[(x, y)]                for cell in wires.pop(wire):                    del owner[cell]  # 값을 0으로 바꾸는 것이 아니라 열쇠를 지운다                out.append(f"removed {wire}")            else:                out.append("none")    out.append(f"{len(wires)} {len(owner)}")    print("\n".join(out))  main()

const lines = require("fs").readFileSync(0, "utf8").split("\n"); const STEP = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };const q = Number(lines[0]);const owner = new Map(); // "x,y" → 전선 번호. 배열 [x, y]는 내용이 같아도 다른 열쇠라서 문자열로 만든다const wires = new Map(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들let nextId = 1;const out = [];for (let t = 1; t <= q; t++) {  const parts = lines[t].trim().split(" ");  let x = Number(parts[1]);  let y = Number(parts[2]);  if (parts[0] === "lay") {    const path = [x + "," + y];    for (const ch of parts[3]) {      x += STEP[ch][0];      y += STEP[ch][1];      path.push(x + "," + y);    }    const hit = path.find((key) => owner.has(key)); // 길 순서로 처음 막히는 칸    if (hit !== undefined) {      out.push("blocked " + owner.get(hit)); // 아무 칸도 놓지 않는다      continue;    }    const mine = [...new Set(path)]; // 자기 길을 다시 지나는 칸은 한 번만    for (const key of mine) owner.set(key, nextId);    wires.set(nextId, mine);    out.push("ok " + mine.length);    nextId++;  } else {    const key = x + "," + y;    if (owner.has(key)) {      const wire = owner.get(key);      for (const k of wires.get(wire)) owner.delete(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다      wires.delete(wire);      out.push("removed " + wire);    } else {      out.push("none");    }  }}out.push(wires.size + " " + owner.size);console.log(out.join("\n"));

import { readFileSync } from "node:fs"; const lines: string[] = readFileSync(0, "utf8").split("\n"); const STEP: Record<string, [number, number]> = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };const q: number = Number(lines[0]);const owner = new Map<string, number>();   // "x,y" → 전선 번호. 배열 [x, y]는 내용이 같아도 다른 열쇠라서 문자열로 만든다const wires = new Map<number, string[]>(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들let nextId = 1;const out: string[] = [];for (let t = 1; t <= q; t++) {  const parts: string[] = lines[t].trim().split(" ");  let x = Number(parts[1]);  let y = Number(parts[2]);  if (parts[0] === "lay") {    const path: string[] = [x + "," + y];    for (const ch of parts[3]) {      x += STEP[ch][0];      y += STEP[ch][1];      path.push(x + "," + y);    }    const hit: string | undefined = path.find((key: string) => owner.has(key)); // 길 순서로 처음 막히는 칸    if (hit !== undefined) {      out.push("blocked " + owner.get(hit)); // 아무 칸도 놓지 않는다      continue;    }    const mine: string[] = [...new Set(path)]; // 자기 길을 다시 지나는 칸은 한 번만    for (const key of mine) owner.set(key, nextId);    wires.set(nextId, mine);    out.push("ok " + mine.length);    nextId++;  } else {    const key: string = x + "," + y;    const wire: number | undefined = owner.get(key);    if (wire !== undefined) {      for (const k of wires.get(wire) ?? []) owner.delete(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다      wires.delete(wire);      out.push("removed " + wire);    } else {      out.push("none");    }  }}out.push(wires.size + " " + owner.size);console.log(out.join("\n"));

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.HashMap;import java.util.LinkedHashSet;import java.util.List;import java.util.Map;import java.util.Set; public class Main {    // 두 좌표를 long 하나로 묶는다. y가 음수이면 위쪽 32비트가 모두 1이 되므로 아래 32비트만 남기고 합친다.    static long key(int x, int y) {        return ((long) x << 32) | (y & 0xFFFFFFFFL);    }     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        int q = Integer.parseInt(in.readLine().trim());        Map<Long, Integer> owner = new HashMap<>();      // 칸 → 전선 번호        Map<Integer, List<Long>> wires = new HashMap<>(); // 전선 번호 → 그 전선이 차지한 칸들        int nextId = 1;        StringBuilder out = new StringBuilder();        for (int t = 0; t < q; t++) {            String[] parts = in.readLine().trim().split(" ");            int x = Integer.parseInt(parts[1]), y = Integer.parseInt(parts[2]);            if (parts[0].equals("lay")) {                Set<Long> mine = new LinkedHashSet<>(); // 자기 길을 다시 지나는 칸은 한 번만                mine.add(key(x, y));                for (char ch : parts[3].toCharArray()) {                    if (ch == 'U') y++;                    else if (ch == 'D') y--;                    else if (ch == 'L') x--;                    else x++;                    mine.add(key(x, y));                }                Integer hit = null;                for (long k : mine) { // LinkedHashSet은 넣은 순서 = 길 순서                    hit = owner.get(k);                    if (hit != null) break;                }                if (hit != null) {                    out.append("blocked ").append(hit).append('\n'); // 아무 칸도 놓지 않는다                    continue;                }                for (long k : mine) owner.put(k, nextId);                wires.put(nextId, new ArrayList<>(mine));                out.append("ok ").append(mine.size()).append('\n');                nextId++;            } else {                Integer wire = owner.get(key(x, y));                if (wire != null) {                    for (long k : wires.remove(wire)) owner.remove(k); // 열쇠를 지운다                    out.append("removed ").append(wire).append('\n');                } else {                    out.append("none\n");                }            }        }        out.append(wires.size()).append(' ').append(owner.size()).append('\n');        System.out.print(out);    }}

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int q = int.Parse(Console.ReadLine().Trim());        var owner = new Dictionary<(int, int), int>();       // 칸 → 전선 번호. 값 튜플은 값이 같으면 같은 열쇠다        var wires = new Dictionary<int, List<(int, int)>>(); // 전선 번호 → 그 전선이 차지한 칸들        int nextId = 1;        var sb = new StringBuilder();        for (int t = 0; t < q; t++)        {            string[] parts = Console.ReadLine().Trim().Split(' ');            int x = int.Parse(parts[1]), y = int.Parse(parts[2]);            if (parts[0] == "lay")            {                var path = new List<(int, int)> { (x, y) };                foreach (char ch in parts[3])                {                    if (ch == 'U') y++;                    else if (ch == 'D') y--;                    else if (ch == 'L') x--;                    else x++;                    path.Add((x, y));                }                int hit = 0;                foreach (var cell in path)                {                    if (owner.TryGetValue(cell, out hit)) break; // 길 순서로 처음 막히는 칸                    hit = 0;                }                if (hit != 0)                {                    sb.Append("blocked ").Append(hit).Append('\n'); // 아무 칸도 놓지 않는다                    continue;                }                var mine = new List<(int, int)>();                foreach (var cell in path)                {                    if (owner.TryAdd(cell, nextId)) mine.Add(cell); // 자기 길을 다시 지나는 칸은 한 번만                }                wires[nextId] = mine;                sb.Append("ok ").Append(mine.Count).Append('\n');                nextId++;            }            else            {                if (owner.TryGetValue((x, y), out int wire))                {                    foreach (var cell in wires[wire]) owner.Remove(cell); // 열쇠를 지운다                    wires.Remove(wire);                    sb.Append("removed ").Append(wire).Append('\n');                }                else                {                    sb.Append("none\n");                }            }        }        sb.Append(wires.Count).Append(' ').Append(owner.Count).Append('\n');        Console.Write(sb);    }}

#include <iostream>#include <map>#include <string>#include <utility>#include <vector>using namespace std; int main() {    int q;    cin >> q;    map<pair<int, int>, int> owner;            // 칸 → 전선 번호. pair는 값으로 비교된다    map<int, vector<pair<int, int>>> wires;    // 전선 번호 → 그 전선이 차지한 칸들    int nextId = 1;    for (int t = 0; t < q; t++) {        string cmd;        int x, y;        cin >> cmd >> x >> y;        if (cmd == "lay") {            string steps;            cin >> steps;            vector<pair<int, int>> path = {{x, y}};            for (char ch : steps) {                if (ch == 'U') y++;                else if (ch == 'D') y--;                else if (ch == 'L') x--;                else x++;                path.push_back({x, y});            }            int hit = 0;            for (const auto& cell : path) {                auto it = owner.find(cell); // owner[cell]로 물으면 없는 칸이 0으로 생겨 버린다                if (it != owner.end()) { hit = it->second; break; }            }            if (hit != 0) {                cout << "blocked " << hit << "\n"; // 아무 칸도 놓지 않는다                continue;            }            vector<pair<int, int>> mine;            for (const auto& cell : path) {                if (owner.insert({cell, nextId}).second) mine.push_back(cell); // 자기 길을 다시 지나는 칸은 한 번만            }            cout << "ok " << mine.size() << "\n";            wires[nextId] = mine;            nextId++;        } else {            auto it = owner.find({x, y});            if (it != owner.end()) {                int wire = it->second;                for (const auto& cell : wires[wire]) owner.erase(cell); // 열쇠를 지운다                wires.erase(wire);                cout << "removed " << wire << "\n";            } else {                cout << "none\n";            }        }    }    cout << wires.size() << " " << owner.size() << "\n";    return 0;}

#include <stdio.h>#include <string.h> /* C에는 사전이 없어서 해시 표를 직접 만든다.   칸은 (x, y, 전선 번호)이고, 빈 칸은 state 0, 쓰는 칸은 1, 지운 자리는 2(찾을 때 건너뛰고 계속 본다). */#define SLOTS (1 << 19) /* 놓는 칸은 모두 합쳐 2,000 × 101 = 202,000개 이하라 표가 차지 않는다 */#define MAXQ 2000#define MAXLEN 100 static int slot_x[SLOTS], slot_y[SLOTS], slot_id[SLOTS];static char state[SLOTS];static int wire_x[MAXQ + 1][MAXLEN + 1], wire_y[MAXQ + 1][MAXLEN + 1], wire_cells[MAXQ + 1]; static unsigned hash(int x, int y) {    unsigned h = (unsigned)x * 2654435761u ^ ((unsigned)y * 40503u + 0x9e3779b9u);    h ^= h >> 15;    return h & (SLOTS - 1);} /* (x, y)가 든 자리를 돌려준다. 없으면 -1 */static int find(int x, int y) {    unsigned h = hash(x, y);    while (state[h] != 0) {        if (state[h] == 1 && slot_x[h] == x && slot_y[h] == y) return (int)h;        h = (h + 1) & (SLOTS - 1);    }    return -1;} static void insert(int x, int y, int id) {    unsigned h = hash(x, y);    while (state[h] == 1) h = (h + 1) & (SLOTS - 1);    state[h] = 1;    slot_x[h] = x;    slot_y[h] = y;    slot_id[h] = id;} int main(void) {    int q;    if (scanf("%d", &q) != 1) return 0;    int next_id = 1, wire_count = 0, cell_count = 0;    for (int t = 0; t < q; t++) {        char cmd[8];        int x, y;        if (scanf("%7s %d %d", cmd, &x, &y) != 3) return 0;        if (strcmp(cmd, "lay") == 0) {            char steps[MAXLEN + 2];            if (scanf("%101s", steps) != 1) return 0;            int len = (int)strlen(steps);            int px[MAXLEN + 1], py[MAXLEN + 1];            px[0] = x;            py[0] = y;            for (int i = 0; i < len; i++) {                if (steps[i] == 'U') y++;                else if (steps[i] == 'D') y--;                else if (steps[i] == 'L') x--;                else x++;                px[i + 1] = x;                py[i + 1] = y;            }            int hit = 0;            for (int i = 0; i <= len && hit == 0; i++) {                int at = find(px[i], py[i]); /* 길 순서로 처음 막히는 칸 */                if (at >= 0) hit = slot_id[at];            }            if (hit != 0) {                printf("blocked %d\n", hit); /* 아무 칸도 놓지 않는다 */                continue;            }            int n = 0;            for (int i = 0; i <= len; i++) {                if (find(px[i], py[i]) >= 0) continue; /* 자기 길을 다시 지나는 칸은 한 번만 */                insert(px[i], py[i], next_id);                wire_x[next_id][n] = px[i];                wire_y[next_id][n] = py[i];                n++;            }            wire_cells[next_id] = n;            wire_count++;            cell_count += n;            printf("ok %d\n", n);            next_id++;        } else {            int at = find(x, y);            if (at >= 0) {                int wire = slot_id[at];                for (int i = 0; i < wire_cells[wire]; i++) state[find(wire_x[wire][i], wire_y[wire][i])] = 2;                wire_count--;                cell_count -= wire_cells[wire];                printf("removed %d\n", wire);            } else {                printf("none\n");            }        }    }    printf("%d %d\n", wire_count, cell_count);    return 0;}

q = 控制台.读行().转数字();owner = 字典(); // "x,y" → 전선 번호. 열쇠는 두 좌표를 쉼표로 이은 문자열wires = 字典(); // 전선 번호 → 그 전선이 차지한 칸의 열쇠들nextId = 1;循环 (t = 0; t < q; t++){    parts = 控制台.读行().去空白().分割(" ");    x = parts[1].转数字();    y = parts[2].转数字();    如果 (parts[0] == "lay")    {        path = ["" + x + "," + y];        steps = parts[3];        循环 (i = 0; i < steps.长度; i++)        {            ch = steps.截取(i, 1);            如果 (ch == "U")            {                y = y + 1;            }            否则 如果 (ch == "D")            {                y = y - 1;            }            否则 如果 (ch == "L")            {                x = x - 1;            }            否则            {                x = x + 1;            }            path.添加("" + x + "," + y);        }        hit = 0;        遍历 (key 在 path)        {            如果 (owner.包含(key))            {                hit = owner[key]; // 길 순서로 처음 막히는 칸                跳出;            }        }        如果 (hit != 0)        {            控制台.输出("blocked " + hit); // 아무 칸도 놓지 않는다        }        否则        {            mine = [];            遍历 (key 在 path)            {                如果 (!owner.包含(key))                {                    owner[key] = nextId;                    mine.添加(key);                }            }            wires[nextId] = mine;            控制台.输出("ok " + mine.数量);            nextId = nextId + 1;        }    }    否则    {        key = "" + x + "," + y;        如果 (owner.包含(key))        {            wire = owner[key];            遍历 (k 在 wires[wire])            {                owner.移除(k); // 값을 바꾸는 것이 아니라 열쇠를 지운다            }            wires.移除(wire);            控制台.输出("removed " + wire);        }        否则        {            控制台.输出("none");        }    }}控制台.输出(wires.数量 + " " + owner.数量);