广东企业网站seo报价,经典重庆论坛新闻论坛,一个完整的策划方案范文,电子商务网站建设方案书题目链接#xff1a; https://vjudge.net/problem/UVA-519 思路#xff1a; 剪枝回溯 这个题巧妙的是他按照表格的位置开始搜索#xff0c;也就是说表格是定的#xff0c;他不断用已有的图片从(0,0)开始拼到(n-1,m-1) 剪枝的地方#xff1a; 1.由于含F的面只能拼到边上 https://vjudge.net/problem/UVA-519 思路 剪枝回溯 这个题巧妙的是他按照表格的位置开始搜索也就是说表格是定的他不断用已有的图片从(0,0)开始拼到(n-1,m-1) 剪枝的地方 1.由于含F的面只能拼到边上所以F的个数就是矩形的周长 2.含O的数目应该和含I的数目相等 3.可能会有很多重复的碎片如果前面的碎片不能拼上去那么后面重复的碎片也不能拼上去 坑点 题目中明明说了只有15块碎片但是将数组大小开到20却WA说明碎片数目已经超过15个 #include iostream
#includecstring
#includealgorithm
using namespace std;
char maze[100][5];
int n,m;
int F0,I0,O0;
int vis[100];
char loc[100][100][5];
int cmp(const void *a,const void *b){return strcmp((char*)a,(char*)b);//strcmp()不能直接判断二维数组的大小
}
int check(int cur,int i,int j){//top, right, bottom, and leftif(i0maze[cur][0]!F) return 0;if(in-1maze[cur][2]!F) return 0;if(j0maze[cur][3]!F) return 0;if(jm-1maze[cur][1]!F) return 0;if(i0(maze[cur][0]loc[i-1][j][2]!IO)) return 0;if(j0(maze[cur][3]loc[i][j-1][1]!IO)) return 0;return 1;
}
int dfs(int x,int y,int cnt){if(cntn*m){//return 1;}char tmp[5]{0};for(int k0;kn*m;k){if(!vis[k](strcmp(tmp,maze[k])!0)check(k,x,y)){strcpy(tmp,maze[k]);strcpy(loc[x][y],maze[k]);vis[k]1;if(dfs((cnt1)/m,(cnt1)%m,cnt1)) return 1;vis[k]0;}} return 0;
}
void init(){memset(maze,0,sizeof(maze));memset(vis,0,sizeof(vis));memset(loc,0,sizeof(loc));F0,I0,O0;
}
int main(int argc, char** argv) {while(scanf(%d %d,n,m)!EOF){if(n0m0) break;init();for(int i0;in*m;i){scanf(%s,maze[i]);for(int j0;j4;j){if(maze[i][j]F) F;else if(maze[i][j]I) I;else if(maze[i][j]O) O;}}if(F!(mn)*2||I!O){printf(NO\n);}else{qsort(maze[0],n*m,sizeof(maze[0]),cmp);//q int Finddfs(0,0,0);if(Find) printf(YES\n);else printf(NO\n);}}return 0;
} 转载于:https://www.cnblogs.com/zhuixunfighting/p/10048804.html
