久しぶりにやっておこう、そして書いておこうと思って。
4月から社会人になったものの、IT企業でもないし、そういう部署でもないから、
全くプログラミングをしていません。
たまにはやろうということで、1ヶ月前くらいにあったAtCoder Typical Contestの初回を途中まで解きました。
3問目は、数学的な内容っぽいなぁと思い、やってないです。典型なんですね。
今回はスルーです。スルーはよくないことだと思います。僕は。
というわけで、A問題。
これは、書いたことあるので、なんとか自力で解けました。
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
InputReader sc = new InputReader(System.in);
int h = sc.nextInt();
int w = sc.nextInt();
String[] sstr = new String[h];
for(int i = 0; i < h; i++){
sstr[i] = sc.nextStr();
}
int[][] stage = new int[h][w];
int xgoal = -1;
int ygoal = -1;
LinkedList<Integer> xqueue = new LinkedList<Integer>();
LinkedList<Integer> yqueue = new LinkedList<Integer>();
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
char ccc = sstr[i].charAt(j);
if(ccc == '#'){//壁
stage[i][j] = 0;
}else if(ccc == '.'){//通れる
stage[i][j] = 1;
}else if(ccc == 's'){//スタート
stage[i][j] = 0;
xqueue.add(i);
yqueue.add(j);
}else{
stage[i][j] = 1;
xgoal = i;
ygoal = j;
}
}
}
boolean clear = false;
while(!xqueue.isEmpty()){
int nowh = xqueue.poll();
int noww = yqueue.poll();
if(stage[nowh][noww] == 2){
clear = true;
break;
}
if(nowh >= 1 && stage[nowh-1][noww] >= 1){
xqueue.push(nowh-1);
yqueue.push(noww);
if(xgoal == nowh-1 && ygoal == noww){
clear = true;
break;
}
}
if(noww >= 1 && stage[nowh][noww-1] >= 1){
xqueue.push(nowh);
yqueue.push(noww-1);
if(xgoal == nowh && ygoal == noww-1){
clear = true;
break;
}
}
if(nowh < h-1 && stage[nowh+1][noww] >= 1){
xqueue.push(nowh+1);
yqueue.push(noww);
if(xgoal == nowh+1 && ygoal == noww){
clear = true;
break;
}
}
if(noww < w-1 && stage[nowh][noww+1] >= 1){
xqueue.push(nowh);
yqueue.push(noww+1);
if(xgoal == nowh && ygoal == noww+1){
clear = true;
break;
}
}
stage[nowh][noww] = 0;
}
if(clear){
System.out.println("Yes");
}else{
System.out.println("No");
}
}
//nextChar を追加したよ！
//System.out.printf("? %d %d\n", i, j);
// LinkedList<Integer>[] setsu = new LinkedList[n];
// for(int i = 0; i < n; i++){
// setsu[i] = new LinkedList<Integer>();
// }
//ここからテンプレ
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int next() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public String nextStr() {
int c = next();
while(isSpaceChar(c)){c = next();}
StringBuffer str = new StringBuffer();
do{
str.append((char)c);
c = next();
}while(!isSpaceChar(c));
return str.toString();
}
public char nextChar() {
int c = next();
while(isSpaceChar(c)){c = next();}
char ret;
do{
ret = (char)c;
c = next();
}while(!isSpaceChar(c));
return ret;
}
public int nextInt() {
int c = next();
while (isSpaceChar(c))
c = next();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = next();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = next();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}よしよし。ただ、なんか一発でなかったりと、コツコツやることの大切さを痛感しました。
そしてB問題。
こちらは、JavaでUnion Findを解いたことがなかったので、良い練習になったと思います。
解説を参考にしました。
頑張ってクラスを作りました。privateがどうとかはやってないです。何故かと言うと、よく分かんないからです。
こんな感じのコードになりました。ちなみに、繋ぎ直しはやりましたが、ランクがどうとかはやってないです(解説を参照)。
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
class UnionFindTree{
//各ノードの親を保管するリスト。親がもうない場合は-1。
private int[] ufTree;
public UnionFindTree(int num){
ufTree = new int[num];
for(int i = 0; i < num; i++){
ufTree[i] = -1;
}
}
public void doUnion(int a, int b){
if(a == b){return;}
int aend = a;
int bend = b;
LinkedList<Integer> pasta = new LinkedList<Integer>();
LinkedList<Integer> pastb = new LinkedList<Integer>();
pasta.push(aend); pastb.push(bend);
while(ufTree[aend] >= 0){
aend = ufTree[aend];
pasta.push(aend);
}
while(ufTree[bend] >= 0){
bend = ufTree[bend];
pastb.push(bend);
}
if(aend == bend){
return;
}else if(aend > bend){
while(!pasta.isEmpty()){
int anode = pasta.pop();
ufTree[anode] = bend;
}
}else{
while(!pastb.isEmpty()){
int bnode = pastb.pop();
ufTree[bnode] = aend;
}
}
//あるノードの親は、自分より小さい番号になる
}
public boolean ask(int a, int b){
if(a == b){return true;}
int aend = a;
while(ufTree[aend] >= 0){
aend = ufTree[aend];
}
int bend = b;
while(ufTree[bend] >= 0){
bend = ufTree[bend];
}
return aend == bend;
}
}
public class Main {
public static void main(String[] args) {
InputReader sc = new InputReader(System.in);
int n = sc.nextInt();
int qnum = sc.nextInt();
UnionFindTree u = new UnionFindTree(n);
for(int qcount = 0; qcount < qnum; qcount++){
int qnumber = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
if(qnumber == 0){
u.doUnion(a, b);
}else{
System.out.println(u.ask(a, b) ? "Yes" : "No");
}
}
}
//nextChar を追加したよ！
//System.out.printf("? %d %d\n", i, j);
// LinkedList<Integer>[] setsu = new LinkedList[n];
// for(int i = 0; i < n; i++){
// setsu[i] = new LinkedList<Integer>();
// }
//ここからテンプレ
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int next() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public String nextStr() {
int c = next();
while(isSpaceChar(c)){c = next();}
StringBuffer str = new StringBuffer();
do{
str.append((char)c);
c = next();
}while(!isSpaceChar(c));
return str.toString();
}
public char nextChar() {
int c = next();
while(isSpaceChar(c)){c = next();}
char ret;
do{
ret = (char)c;
c = next();
}while(!isSpaceChar(c));
return ret;
}
public int nextInt() {
int c = next();
while (isSpaceChar(c))
c = next();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = next();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = next();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}こういうのって蓄積していくべきなんでしょうか。
でも、ちゃんとコメントいっぱい書くなりノートみたいなの作るとかしないと、後で使った時によく分かんなくなりそうですよね・・・
日々いっぱい問題解いて、統一感のあるコードを書いてたら大丈夫なんでしょうが。
迷うところです。
これから、どうしましょうか。プログラミングは続けたいんですが。
アプリ開発とかWeb開発とかみたいな方向に行くか、競技やるか、データ分析のやつやるか・・・
なんとか、なんかしようと思います。なんとかしてなんかするぞ〜！
おわり
