UVA11846 找座位


1 #include<cstdlib> 2 #include<algorithm> 3 #include<iostream> 4 #include<cstdio> 5 #include<cstring> 6 using namespace std; 7 8 //写小组类(组长坐标,可能的位置) 9 //先循环确定各小组的可能位置数 10 //X操作: 确定位置数为一的小组,更新地图,更新位置数非一的小组。循环(位置数小于一则无解) 11 //当某次循环后所有小组位置数均大于一(进入dfs循环) 12 //两种操作1:假定一个小组位置,继续X操作 2:枚举所有小组位置可能的情况,判断是否冲突 13 //这里用第一个方法,第一个要回溯,map数组在函数中重建,这样不影响X操作对map数组的改变 14 15 struct xz 16 { 17 int x, y; 18 int n; 19 int ant; 20 int Nx[30], Ny[30], Tx[30], Ty[30];//形状和队长位置 21 }; 22 23 const int MAXN = 20; 24 int n, k, Map; 25 26 int map[20][20]; 27 xz XZ[30]; 28 29 void init(xz *qwe) 30 { 31 Map = 0; 32 memset(map, -1, sizeof(map)); 33 for (int i = 0; i < k; i++) 34 { 35 qwe[i].ant = qwe[i].n = qwe[i].x = qwe[i].y = -1; 36 memset(qwe[i].Nx, 0, sizeof(qwe[i].Nx)); 37 memset(qwe[i].Ny, 0, sizeof(qwe[i].Ny)); 38 memset(qwe[i].Tx, 0, sizeof(qwe[i].Tx)); 39 memset(qwe[i].Ty, 0, sizeof(qwe[i].Ty)); 40 } 41 char q; int x = 0; 42 for (int i = 0; i < n; i++) 43 for (int j = 0; j < n; j++) 44 { 45 cin >> q; 46 if (q != '.') 47 { 48 XZ[x].x = i; 49 XZ[x].y = j; 50 XZ[x].n = q - '0'; 51 x++; 52 map[i][j] = Map++; 53 } 54 } 55 } 56 57 bool ok(int nx, int ny, int x, int y,xz &a) 58 { 59 int Ok = 1; 60 for (int i = 0; i < nx; i++) 61 for (int j = 0; j < ny; j++) 62 { 63 if (x + i < 0 || x + i >= n || j + y < 0 || j + y >= n || (map[x + i][y + j]!=-1&&(a.x!=x+i||a.y!=y+j))) 64 { 65 Ok = 0; break; 66 } 67 if (!Ok)break; 68 } 69 if (Ok) 70 return true; 71 return false; 72 } 73 74 int renew(xz &qwe,int asd) 75 { 76 if (qwe.ant == -1) 77 { 78 for (int nx = 1; nx <= qwe.n; nx++) 79 { 80 if (qwe.n%nx)continue; 81 int ny = qwe.n / nx; 82 for (int x = 0; x < nx; x++) 83 for (int y = 0; y < ny; y++) 84 { 85 if (ok(nx, ny, qwe.x - x, qwe.y - y,qwe)) 86 { 87 qwe.ant++; 88 qwe.Nx[qwe.ant] = nx; 89 qwe.Ny[qwe.ant] = ny; 90 qwe.Tx[qwe.ant] = x; 91 qwe.Ty[qwe.ant] = y; 92 } 93 } 94 } 95 qwe.ant++; 96 if (qwe.ant == 1) 97 { 98 for (int i = 0; i < qwe.Nx[0]; i++) 99 for (int j = 0; j < qwe.Ny[0]; j++) 100 map[qwe.x - qwe.Tx[0] + i][qwe.y - qwe.Ty[0] + j] = asd; 101 } 102 return qwe.ant+1; 103 } 104 else if (qwe.ant > 1) 105 { 106 int ant = 0; 107 for (int i = 0; i < qwe.ant; i++) 108 { 109 if (!ok(qwe.Nx[i], qwe.Ny[i], qwe.x - qwe.Tx[i], qwe.y - qwe.Ty[i],qwe)) 110 { 111 ant++; 112 for (int j = i; j < qwe.ant - 1; j++) 113 { 114 qwe.Nx[j] = qwe.Nx[j + 1]; 115 qwe.Ny[j] = qwe.Ny[j + 1]; 116 qwe.Tx[j] = qwe.Tx[j + 1]; 117 qwe.Ty[j] = qwe.Ty[j + 1]; 118 } 119 i--; qwe.ant--; 120 } 121 } 122 if (qwe.ant == 1) 123 { 124 for (int i = 0; i < qwe.Nx[0]; i++) 125 for (int j = 0; j < qwe.Ny[0]; j++) 126 map[qwe.x - qwe.Tx[0] + i][qwe.y - qwe.Ty[0] + j] = asd; 127 } 128 if (ant) 129 return 1; 130 } 131 return 0; 132 } 133 134 int solve(int &ans) 135 { 136 ans = 0; 137 int ant = 0; 138 for (int i = 0; i < k; i++) 139 { 140 if (XZ[i].ant == 1) 141 { 142 ans++; continue; 143 } 144 if (renew(XZ[i] ,i)) 145 ant++; 146 if (XZ[i].ant == 0) 147 return 0; 148 } 149 if (ans == k) 150 return 1; 151 int a = 0; 152 if (ant) 153 if (!solve(a)) 154 return 0; 155 if (a == k) 156 ans = a; 157 return 1; 158 } 159 160 void Print() 161 { 162 int X[30], x = 0; 163 memset(X, -1, sizeof(X)); 164 for (int i = 0; i < n; i++) 165 for (int j = 0; j < n; j++) 166 if (X[map[i][j]] == -1) 167 X[map[i][j]] = x++; 168 for (int i = 0; i < n; i++) 169 { 170 for (int j = 0; j < n; j++) 171 printf("%c", 'A' + X[map[i][j]]); 172 printf("\n"); 173 } 174 } 175 176 int dfs() 177 { 178 for (int i = 0; i < k; i++) 179 { 180 if (XZ[i].ant != 1) 181 { 182 int ant; 183 ant = XZ[i].ant; 184 XZ[i].ant = 1; 185 for (int t = 0; t < ant; t++) 186 { 187 int Map[MAXN][MAXN]; 188 memcpy(Map, map, sizeof(map)); 189 xz XZ1[30]; 190 for (int i = 0; i < k; i++) 191 XZ1[i] = XZ[i]; 192 for (int j = 0; j < XZ[i].Nx[t]; j++) 193 for (int k = 0; k < XZ[i].Ny[t]; k++) 194 map[XZ[i].x - XZ[i].Tx[t] + j][XZ[i].y - XZ[i].Ty[t] + k] = i; 195 int ans = 0; 196 int v=solve(ans); 197 if (v != 0) 198 { 199 if (ans == k) 200 { 201 Print(); 202 return 1; 203 } 204 if (dfs()) 205 return 1; 206 } 207 memcpy(map, Map, sizeof(map)); 208 for (int i = 0; i < k; i++) 209 XZ[i] = XZ1[i]; 210 } 211 } 212 } 213 return 0; 214 } 215 216 int main() 217 { 218 while (scanf_s("%d%d", &n, &k) == 2 && n != 0) 219 { 220 init(XZ); 221 int a=0; 222 solve(a); 223 if (a != k) 224 dfs(); 225 else 226 Print(); 227 } 228 return 0; 229 }
//自己写的垃圾。。。

 

上一篇:python中的列表


下一篇:Vue学习——使用v-for渲染后,改变列表里的某个数据并可以二次渲染