#845797 (cLay) No.2238 Rock and Hole

• 問題: No.2238 Rock and Hole
• ユーザー: tails
• 提出日時: 2023-03-03 22:29:43
• 言語: cLay (20240104-1)
• 結果: AC
• 実行時間: 46 ms / 3,000 ms
• コード長: 770 bytes
• コンパイル時間: 6,509 ms
• コンパイル使用メモリ: 180,968 KB
• 実行使用メモリ: 20,908 KB
• 最終ジャッジ日時: 2023-10-18 02:38:30
• 合計ジャッジ時間: 7,962 ms
• ジャッジサーバーID （参考情報）: judge13 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 7,756 KB
testcase_01	AC	2 ms; 7,756 KB
testcase_02	AC	2 ms; 7,756 KB
testcase_03	AC	3 ms; 7,756 KB
testcase_04	AC	3 ms; 7,756 KB
testcase_05	AC	3 ms; 7,756 KB
testcase_06	AC	3 ms; 7,756 KB
testcase_07	AC	2 ms; 7,756 KB
testcase_08	AC	2 ms; 7,756 KB
testcase_09	AC	3 ms; 7,756 KB
testcase_10	AC	6 ms; 10,232 KB
testcase_11	AC	21 ms; 17,948 KB
testcase_12	AC	20 ms; 17,560 KB
testcase_13	AC	18 ms; 16,952 KB
testcase_14	AC	11 ms; 12,652 KB
testcase_15	AC	6 ms; 9,704 KB
testcase_16	AC	25 ms; 20,908 KB
testcase_17	AC	35 ms; 20,896 KB
testcase_18	AC	25 ms; 20,880 KB
testcase_19	AC	30 ms; 14,316 KB
testcase_20	AC	29 ms; 15,408 KB
testcase_21	AC	46 ms; 14,784 KB
testcase_22	AC	19 ms; 14,832 KB
testcase_23	AC	2 ms; 7,756 KB

ソースコード

ll@h,@w,n=0;
string@s[h];
maxflow<int,int>f;
f.malloc(h*w+2,1);

rep(y,h){
	int r=-1;
	rep(x,w){
		int c=s[y][x];
		if(c=='h'){
			f.addEdge(h*w,y*w+x,1,0);
			r=x;
		}
		if(c=='r'){
			++n;
			f.addEdge(y*w+x,h*w+1,1,0);
			if(r>=0){
				f.addEdge(y*w+r,y*w+x,1,0);
			}
		}
	}
}

rep(y,h){
	int r=-1;
	rrep(x,w){
		int c=s[y][x];
		if(c=='h'){
			r=x;
		}
		if(c=='r'){
			if(r>=0){
				f.addEdge(y*w+r,y*w+x,1,0);
			}
		}
	}
}

rep(x,w){
	int r=-1;
	rep(y,h){
		int c=s[y][x];
		if(c=='h'){
			r=y;
		}
		if(c=='r'){
			if(r>=0){
				f.addEdge(r*w+x,y*w+x,1,0);
			}
		}
	}
}

rep(x,w){
	int r=-1;
	rrep(y,h){
		int c=s[y][x];
		if(c=='h'){
			r=y;
		}
		if(c=='r'){
			if(r>=0){
				f.addEdge(r*w+x,y*w+x,1,0);
			}
		}
	}
}

wt(f.solve(h*w,h*w+1)==n?"Yes":"No");