2011-08-26 07:50:03Morris
a219. 限制排列
a219. 限制排列
/**********************************************************************************/
/* Problem: a219 "限制排列" from DFS */
/* Language: C */
/* Result: AC (420ms, 188KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-25 11:47:11 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int map[20][20] = {}, n;
char Way[20], Last[20];
int next[20];
void DFS(int now, int set) {
int a, pre = 0;
if(now == 0) {
for(a = 0; a < set; a++) {
if(Way[a]-1+'A' != Last[a])
Last[a] = Way[a]-1+'A', putchar(Last[a]);
}
puts("");
return;
}
for(a = next[0]; a; pre = a, a = next[a])
if(!map[a][set]){
next[pre] = next[a];
Way[set] = a;
DFS(now-1, set+1);
next[pre] = a;
}
}
main() {
int a, x;
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
next[a] = a+1;
memset(Last, 0, sizeof(Last));
memset(map, 0, sizeof(map));
for(a = 1; a <= n; a++) {
while(scanf("%d", &x) == 1 && x != 0)
map[a][x-1] = 1;
}
next[n] = 0;
DFS(n, 0);
}
return 0;
}
輸出優化版本
/**********************************************************************************/
/* Problem: a219 "限制排列" from DFS */
/* Language: C */
/* Result: AC (252ms, 11992KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-25 12:05:56 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int map[20][20] = {}, n;
char Way[20], Last[20], Ans[20000000], *At;
int next[20];
void DFS(int now, int set) {
int a, pre = 0;
if(now == 0) {
for(a = 0; a < set; a++) {
if(Way[a]-1+'A' != Last[a])
Last[a] = Way[a]-1+'A', *At++ = Last[a];
}
*At++ = '\n';
return;
}
for(a = next[0]; a; pre = a, a = next[a])
if(!map[a][set]){
next[pre] = next[a];
Way[set] = a;
DFS(now-1, set+1);
next[pre] = a;
}
}
main() {
int a, x;
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
next[a] = a+1;
memset(Last, 0, sizeof(Last));
memset(map, 0, sizeof(map));
At = Ans;
for(a = 1; a <= n; a++) {
while(scanf("%d", &x) == 1 && x != 0)
map[a][x-1] = 1;
}
next[n] = 0;
DFS(n, 0);
*At = '\0', puts(Ans);
}
return 0;
}
內容 ：
小光的 DFS 剪枝技巧, 在這個暑假進步了一些些, 但是仍然無法通過 DP 的噩夢,
現在給你 N 個人, 編號分別是 A, B, ... Z, 接著總是會有人不想排哪裡,
請你把所有可能列出來, 但是輸出檔隨便生一生就爆表了 !
因此希望你如果新的排列跟上次一樣的部分就不輸出了, 僅僅輸出不同的部分
輸入說明
：
有多筆測資, 每筆第一行 有一個正整數 N (1 ≦ N ≦ 15),
接下來會有 N 行, 第 N 行代表 第 N 個人不想排的位置, 以 0 代表結束
輸出說明
：
請把所有可能列出來(依照字典順序), 跟上次一樣的部分就不輸出, 僅僅輸出不同的部分
範例輸入 ：
3 0 0 0 3 1 0 3 0 0
範例輸出 ：
ABC CB BAC CA CAB BA BAC CA CB
提示
：
3
0
0
0
原本是
ABC
ACB
BAC
BCA
CAB
CBA
給大家水一下, 不然都說我出題都很邪惡
出處
：
/**********************************************************************************/
/* Problem: a219 "限制排列" from DFS */
/* Language: C */
/* Result: AC (420ms, 188KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-25 11:47:11 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int map[20][20] = {}, n;
char Way[20], Last[20];
int next[20];
void DFS(int now, int set) {
int a, pre = 0;
if(now == 0) {
for(a = 0; a < set; a++) {
if(Way[a]-1+'A' != Last[a])
Last[a] = Way[a]-1+'A', putchar(Last[a]);
}
puts("");
return;
}
for(a = next[0]; a; pre = a, a = next[a])
if(!map[a][set]){
next[pre] = next[a];
Way[set] = a;
DFS(now-1, set+1);
next[pre] = a;
}
}
main() {
int a, x;
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
next[a] = a+1;
memset(Last, 0, sizeof(Last));
memset(map, 0, sizeof(map));
for(a = 1; a <= n; a++) {
while(scanf("%d", &x) == 1 && x != 0)
map[a][x-1] = 1;
}
next[n] = 0;
DFS(n, 0);
}
return 0;
}
輸出優化版本
/**********************************************************************************/
/* Problem: a219 "限制排列" from DFS */
/* Language: C */
/* Result: AC (252ms, 11992KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-25 12:05:56 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int map[20][20] = {}, n;
char Way[20], Last[20], Ans[20000000], *At;
int next[20];
void DFS(int now, int set) {
int a, pre = 0;
if(now == 0) {
for(a = 0; a < set; a++) {
if(Way[a]-1+'A' != Last[a])
Last[a] = Way[a]-1+'A', *At++ = Last[a];
}
*At++ = '\n';
return;
}
for(a = next[0]; a; pre = a, a = next[a])
if(!map[a][set]){
next[pre] = next[a];
Way[set] = a;
DFS(now-1, set+1);
next[pre] = a;
}
}
main() {
int a, x;
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
next[a] = a+1;
memset(Last, 0, sizeof(Last));
memset(map, 0, sizeof(map));
At = Ans;
for(a = 1; a <= n; a++) {
while(scanf("%d", &x) == 1 && x != 0)
map[a][x-1] = 1;
}
next[n] = 0;
DFS(n, 0);
*At = '\0', puts(Ans);
}
return 0;
}
上一篇：d228. kill man
下一篇：a229. 括號匹配問題