代码
比这篇新的文章:
刚刚写的两个javascript Object Clone（对象克隆）函数
比这篇旧的文章: 小题目
作者: xpycc, 点击331次, 评论(0), 收藏者(0)
打分:
所有评论，共0条：( 我也来说两句)
比这篇旧的文章: 小题目
puzzle.cpp
语言: C++, 标签: 无 2008/08/29发布 4个月前更新作者: xpycc, 点击331次, 评论(0), 收藏者(0)
C++语言: puzzle.cpp
001 #include <fstream>
002 #include <cstring>
003 #include <cctype>
004 using namespace std;
005 ifstream fin("puzzle.in");
006 ofstream fout("puzzle.out");
007 #define cout fout
008
009 const int MAXL = 65537 * 2 + 1, pv[10] = {9711, 1237, 6537, 1231, 2173, 7691, 9991, 7321, 5761, 8767};
010
011 const int MAX = 25;
012
013 struct point {
014 int x, y;
015 };
016
017 int n, pos[MAX][MAX], tot, ord[MAX];
018 point p1[MAX], p2[MAX];
019 int map[MAX][MAX];
020 char wmap[MAX][MAX], name[MAX], word[100000+5][10+5], used[100000+5];
021
022 struct hnode {
023 char word[11];
024 int id;
025 hnode* next;
026 };
027
028 hnode* hash[20][MAXL] = {0};
029
030 void insert(char word[], int ord, int id) {
031 int i, v = 0, l = strlen(word);
032 for (i = 0; i < l; i++)
033 if (pos[id][i + 1])
034 v = (v + word[i] * pv[i]) % MAXL * pv[i] % MAXL;
035 v = (v * 2047 + l) % MAXL;
036 hnode* op = new hnode;
037 strcpy(op->word, word);
038 op->id = ord;
039 op->next = hash[id][v];
040 hash[id][v] = op;
041 }
042
043 hnode* find(point p1, point p2, int id) {
044 int i, j, k, v = 0, l = p2.x - p1.x + p2.y - p1.y + 1;
045 for (i = p1.x; i <= p2.x; i++)
046 for (j = p1.y; j <= p2.y; j++)
047 if (pos[id][k = i - p1.x + j - p1.y + 1])
048 v = (v + wmap[i][j] * pv[k - 1]) % MAXL * pv[k - 1] % MAXL;
049 v = (v * 2047 + l) % MAXL;
050 return hash[id][v];
051 }
052
053 void in();
054 void create();
055
056 int sol;
057 char ans[MAX][10+5];
058
059 void search(int lev) {
060 if (lev == n) {
061 sol = 1;
062 return;
063 }
064
065 hnode* op = find(p1[lev], p2[lev], lev);
066 int i, j, k, ok;
067 for (; op; op = op->next) {
068 if (used[op->id]) continue;
069 if ((int)strlen(op->word) != p2[lev].x - p1[lev].x + p2[lev].y - p1[lev].y + 1) continue;
070 ok = 1;
071 for (i = p1[lev].x; ok && i <= p2[lev].x; i++)
072 for (j = p1[lev].y; j <= p2[lev].y; j++)
073 if (pos[lev][k = i - p1[lev].x + j - p1[lev].y + 1])
074 if (wmap[i][j] != op->word[k - 1]) {
075 ok = 0;
076 break;
077 }
078
079 if (ok) {
080 for (i = p1[lev].x; ok && i <= p2[lev].x; i++)
081 for (j = p1[lev].y; j <= p2[lev].y; j++)
082 wmap[i][j] = op->word[i - p1[lev].x + j - p1[lev].y];
083 strcpy(ans[lev], op->word);
084 used[op->id] = 1;
085 search(lev + 1);
086 if (sol) return;
087 used[op->id] = 0;
088 }
089 }
090 }
091
092 int main() {
093 in();
094 create();
095
096 memset(used, 0, sizeof(used));
097 sol = 0;
098 search(0);
099
100 // if (sol == 0) cout << "No solution" << endl;
101
102 int i, j;
103 for (i = 0; i < n; i++)
104 for (j = 0; j < n; j++)
105 if (ord[j] == i) {
106 cout << ans[j] << endl;
107 break;
108 }
109
110 return 0;
111 }
112
113 void in() {
114 fin.getline(name, 100);
115 ifstream fw(name);
116 tot = 0;
117 char cword[30];
118 for (; fw >> cword;)
119 if (strlen(cword) <= 10) {
120 int i;
121 for (i = 0; i < strlen(cword); i++)
122 cword[i] = toupper(cword[i]);
123 strcpy(word[tot++], cword);
124 }
125
126 fin >> n;
127 int i, j;
128 for (i = 0; i < n; i++) {
129 ord[i] = i;
130 fin >> p1[i].x >> p1[i].y; p2[i] = p1[i];
131 char sign; fin >> sign >> j;
132 if (sign == 'A') p2[i].x += j - 1;
133 else p2[i].y += j - 1;
134 }
135 }
136
137 void create() {
138 memset(map, 0, sizeof(map));
139 memset(pos, 0, sizeof(pos));
140 int i, j, k, c;
141 for (c = 0; c < n; c++) {
142 int max = -1, id;
143 for (i = c; i < n; i++) {
144 int tot = 0;
145 for (j = p1[i].x; j <= p2[i].x; j++)
146 for (k = p1[i].y; k <= p2[i].y; k++)
147 if (map[j][k])
148 tot++;
149 if (tot > max) max = tot, id = i;
150 }
151 point tmp;
152 tmp = p1[id], p1[id] = p1[c], p1[c] = tmp;
153 tmp = p2[id], p2[id] = p2[c], p2[c] = tmp;
154 i = ord[id], ord[id] = ord[c], ord[c] = i;
155 i = c;
156
157 pos[i][0] = p2[i].x - p1[i].x + p2[i].y - p1[i].y + 1;
158
159 for (j = p1[i].x; j <= p2[i].x; j++)
160 for (k = p1[i].y; k <= p2[i].y; k++) {
161 if (map[j][k]) pos[i][j - p1[i].x + k - p1[i].y + 1] = 1;
162 map[j][k] = 1;
163 }
164
165 for (j = 0; j < tot; j++)
166 if (pos[i][0] == (int)strlen(word[j]))
167 insert(word[j], j, i);
168 }
169 }
002 #include <cstring>
003 #include <cctype>
004 using namespace std;
005 ifstream fin("puzzle.in");
006 ofstream fout("puzzle.out");
007 #define cout fout
008
009 const int MAXL = 65537 * 2 + 1, pv[10] = {9711, 1237, 6537, 1231, 2173, 7691, 9991, 7321, 5761, 8767};
010
011 const int MAX = 25;
012
013 struct point {
014 int x, y;
015 };
016
017 int n, pos[MAX][MAX], tot, ord[MAX];
018 point p1[MAX], p2[MAX];
019 int map[MAX][MAX];
020 char wmap[MAX][MAX], name[MAX], word[100000+5][10+5], used[100000+5];
021
022 struct hnode {
023 char word[11];
024 int id;
025 hnode* next;
026 };
027
028 hnode* hash[20][MAXL] = {0};
029
030 void insert(char word[], int ord, int id) {
031 int i, v = 0, l = strlen(word);
032 for (i = 0; i < l; i++)
033 if (pos[id][i + 1])
034 v = (v + word[i] * pv[i]) % MAXL * pv[i] % MAXL;
035 v = (v * 2047 + l) % MAXL;
036 hnode* op = new hnode;
037 strcpy(op->word, word);
038 op->id = ord;
039 op->next = hash[id][v];
040 hash[id][v] = op;
041 }
042
043 hnode* find(point p1, point p2, int id) {
044 int i, j, k, v = 0, l = p2.x - p1.x + p2.y - p1.y + 1;
045 for (i = p1.x; i <= p2.x; i++)
046 for (j = p1.y; j <= p2.y; j++)
047 if (pos[id][k = i - p1.x + j - p1.y + 1])
048 v = (v + wmap[i][j] * pv[k - 1]) % MAXL * pv[k - 1] % MAXL;
049 v = (v * 2047 + l) % MAXL;
050 return hash[id][v];
051 }
052
053 void in();
054 void create();
055
056 int sol;
057 char ans[MAX][10+5];
058
059 void search(int lev) {
060 if (lev == n) {
061 sol = 1;
062 return;
063 }
064
065 hnode* op = find(p1[lev], p2[lev], lev);
066 int i, j, k, ok;
067 for (; op; op = op->next) {
068 if (used[op->id]) continue;
069 if ((int)strlen(op->word) != p2[lev].x - p1[lev].x + p2[lev].y - p1[lev].y + 1) continue;
070 ok = 1;
071 for (i = p1[lev].x; ok && i <= p2[lev].x; i++)
072 for (j = p1[lev].y; j <= p2[lev].y; j++)
073 if (pos[lev][k = i - p1[lev].x + j - p1[lev].y + 1])
074 if (wmap[i][j] != op->word[k - 1]) {
075 ok = 0;
076 break;
077 }
078
079 if (ok) {
080 for (i = p1[lev].x; ok && i <= p2[lev].x; i++)
081 for (j = p1[lev].y; j <= p2[lev].y; j++)
082 wmap[i][j] = op->word[i - p1[lev].x + j - p1[lev].y];
083 strcpy(ans[lev], op->word);
084 used[op->id] = 1;
085 search(lev + 1);
086 if (sol) return;
087 used[op->id] = 0;
088 }
089 }
090 }
091
092 int main() {
093 in();
094 create();
095
096 memset(used, 0, sizeof(used));
097 sol = 0;
098 search(0);
099
100 // if (sol == 0) cout << "No solution" << endl;
101
102 int i, j;
103 for (i = 0; i < n; i++)
104 for (j = 0; j < n; j++)
105 if (ord[j] == i) {
106 cout << ans[j] << endl;
107 break;
108 }
109
110 return 0;
111 }
112
113 void in() {
114 fin.getline(name, 100);
115 ifstream fw(name);
116 tot = 0;
117 char cword[30];
118 for (; fw >> cword;)
119 if (strlen(cword) <= 10) {
120 int i;
121 for (i = 0; i < strlen(cword); i++)
122 cword[i] = toupper(cword[i]);
123 strcpy(word[tot++], cword);
124 }
125
126 fin >> n;
127 int i, j;
128 for (i = 0; i < n; i++) {
129 ord[i] = i;
130 fin >> p1[i].x >> p1[i].y; p2[i] = p1[i];
131 char sign; fin >> sign >> j;
132 if (sign == 'A') p2[i].x += j - 1;
133 else p2[i].y += j - 1;
134 }
135 }
136
137 void create() {
138 memset(map, 0, sizeof(map));
139 memset(pos, 0, sizeof(pos));
140 int i, j, k, c;
141 for (c = 0; c < n; c++) {
142 int max = -1, id;
143 for (i = c; i < n; i++) {
144 int tot = 0;
145 for (j = p1[i].x; j <= p2[i].x; j++)
146 for (k = p1[i].y; k <= p2[i].y; k++)
147 if (map[j][k])
148 tot++;
149 if (tot > max) max = tot, id = i;
150 }
151 point tmp;
152 tmp = p1[id], p1[id] = p1[c], p1[c] = tmp;
153 tmp = p2[id], p2[id] = p2[c], p2[c] = tmp;
154 i = ord[id], ord[id] = ord[c], ord[c] = i;
155 i = c;
156
157 pos[i][0] = p2[i].x - p1[i].x + p2[i].y - p1[i].y + 1;
158
159 for (j = p1[i].x; j <= p2[i].x; j++)
160 for (k = p1[i].y; k <= p2[i].y; k++) {
161 if (map[j][k]) pos[i][j - p1[i].x + k - p1[i].y + 1] = 1;
162 map[j][k] = 1;
163 }
164
165 for (j = 0; j < tot; j++)
166 if (pos[i][0] == (int)strlen(word[j]))
167 insert(word[j], j, i);
168 }
169 }
所有评论，共0条：( 我也来说两句)